函数列表中的函数组合！

Question

我需要定义一个函数“Compose”，它接受一个列表“L”，它是一个函数列表。当我指定适合列表中所有函数的参数时，最后一个函数使用此参数评估自身。然后将结果传递给倒数第二个函数，依此类推，直到到达列表中的第一项（函数）并获得最终结果。

例如

Compose ((fn N -> N + 1) ^ (fn N -> 2 * N) ^#) 3 。

给出答案 7。

我必须用一种名为 SAL（简单应用语言）的函数式编程语言来编写这个语言，该语言是由我大学的一位讲师设计的（因此上面的语法很有趣（^ 分隔列表项，# 标记列表结尾））。

如果任何解决方案可以用伪代码编写，记住我不能使用循环、变量等，那将非常感激。显然，解决方案是一行答案。我想它涉及递归（我们 99% 的任务函数都涉及递归！）。

另外我不懂 Haskell（我想我必须学习！）所以伪代码甚至简单的英语都会很棒。 –

非常感谢。

Answer 1

如果解决方案是一行答案，则可能涉及折叠：

compose :: [a -> a] -> a -> a
compose fs v = foldl (flip (.)) id fs $ v

http://haskell.org/haskellwiki /Compose

您还可以将其实现为右折叠，它按照您想要的方式工作：

compose = foldr (.) id

*Main> let compose = foldr (.) id
*Main> compose [\x -> x+1, \x -> 2 * x, id] 3
7

Answer 2

在哈斯克尔：

compose :: a -> [a -> a] -> a
compose a (x:xs) = x (compose a xs)
compose a [] = a

Answer 3

丹有点放弃了，但这里有一个关于如何自己做的提示。您可以对数字进行递归：

0! = 1
n! = (n-1)! * n

您也可以对结构进行递归。例如，列表具有递归结构，分为两种情况：空列表和项目后跟列表的其余部分。在任何特定语言中：

List :=   Item x List 
        | Nil

Item 标记列表的头部，x 是存储在头部的值，List 是尾部。在这个语法中，你的列表将被写成：

Item ( fn N -> N + 1 ) Item ( fn N -> 2 * N ) Nil

你的教授发明的语法中的列表规则可以递归地写为：

List :=   x ^ List
        | #

列表上的函数必须在此结构上递归，这意味着它处理两种情况中的每一种：

sum l:List = Nil -> 0
           | Item x xs:List = x + sum xs

递归具体来说，是术语 sum l:List = x + sum xs。使用教授留下的语法编写这个函数作为练习。

在您的问题中，您的元函数采用函数列表并且必须返回一个函数。考虑每种情况，空列表和一个项目（头部），后面跟着一个列表（尾部）。在后一种情况下，您可以递归地使用函数从尾部获取函数，然后以某种方式将其与头部组合以返回函数。无论如何，这就是要点。

Answer 4

与使用幺半群相同，无点

import Data.Monoid
compose :: [a -> a] -> a -> a
compose = appEndo . mconcat . map Endo

或者更一般地说：

import Data.Monoid
compose :: (Functor t, Foldable t) => t (a -> a) -> a -> a
compose = appEndo . foldl1 (<>) . fmap Endo

Answer 5

这是我使用的：

compose :: [a -> a] -> a -> a
compose list startingvalue = foldl (\x f -> f x) startingvalue list