函数列表中的函数组合!

9
我需要定义一个名为“Compose”的函数,它接受一个列表'L',其中包含多个函数。当我指定一个适用于列表中所有函数的参数时,最后一个函数将使用此参数进行计算。然后将结果传递给倒数第二个函数,以此类推,直到我们到达列表中的第一个项目(函数),并得到最终结果。
例如,
Compose ((fn N -> N + 1)^(fn N -> 2 * N)^#)3。
将给出答案7。
我必须在一种名为SAL(简单应用语言)的函数式编程语言中编写此代码。如果可以用伪代码表示解决方案,请记住我不能使用循环、变量等。显然,答案是一行代码。我想它涉及到递归(我们99%的任务函数都这样!)。
另外,我不懂Haskell(猜测我得学习!),所以伪代码甚至普通英语也很好。 -
非常感谢。
5个回答

17

如果解决方案是一行代码,它可能涉及到fold:

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

在你的第一个版本中,$ 是不必要的,因此你可能想这样写成 pointfree 形式:compose = foldl (flip (.)) id - HaskellElephant
谢谢您的评论,但这并不是我的解决方案,而是从我发布的链接中复制的。 - Michael Kohl
1
如果右折叠具有所需的语义(更懒惰和更高效),则通常对于这种特定类型的事情要好得多。 - dfeuer
2
11年过去了,但是 foldr (.) id = foldr1 (.) 等等 :) - matt

5

在Haskell中:

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

1
相同的使用单子,无点符号
import Data.Monoid
compose :: [a -> a] -> a -> a
compose = appEndo . mconcat . map Endo

或者更普遍地说:

(保留HTML,不解释)
import Data.Monoid
compose :: (Functor t, Foldable t) => t (a -> a) -> a -> a
compose = appEndo . foldl1 (<>) . fmap Endo

4
哦?为什么不直接使用compose :: Foldable t => t (a -> a) -> a -> a; compose = appEndo . foldMap Endo呢? - dfeuer
1
是的,mconcat = foldl1 (<>) = fold,因此 fold . map Endo == foldMap Endo - Will Ness

1
丹有点暴露了它,但这里有一个提示,教你如何自己做。您可以递归处理数字:
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。使用教授的语法编写此函数留作练习。

在您的问题中,您的元函数接受函数列表并必须返回一个函数。考虑每种情况,空列表和一个项(头部)后跟一个列表(尾部)。在后一种情况下,您可以递归使用您的函数从尾部获取函数,然后以某种方式将其与头部组合以返回函数。那就是要点,无论如何。


0

我使用了以下代码:

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接