1

我有一个列表[a,b,c,d,e]和一个初始值u（显然a,b,c,d,e代表值）。我想将一个函数应用于eand u，比如说f(e,u)。然后我想应用该函数f(d, f(e, u))，然后f(c, f(d, f(e, u)))等等。我看过“迭代”，但我无法弄清楚如何将迭代应用到列表中的每个元素。

我的列表：

a = take 101 (0 : concat [[(1%1),(2*k%1),(1%1)] | k <- [1..40]])

我将如何在 Haskell 中实现这一点？

谢谢，山姆。

4

4 回答 4

6

你想要foldr :: (a -> b -> b) -> b -> [a] -> b。这是列表数据结构的一般折叠。将其视为用两个提供的参数替换列表中的所有(:)和构造函数。[]

例如，如果我们要对[1, 2, 3]构造为的列表的数字求和1 : (2 : (3 : []))，我们可以找到 and 的替代品，就像and一样，即。因此，我们可以实现as 。(:)[]+01 + (2 + (3 + 0))sum :: Num a => [a] -> afoldr (+) 0

于 2013-01-24T22:29:25.023 回答
3

您描述的功能称为“折叠”，在这种情况下为“右折叠”，因为它是从右向左应用的。它在 Prelude 中作为foldr函数实现。

例如，如果我们采用(++)连接两个字符串的函数，并将其应用于初始元素和字符串列表：

Prelude> foldr (++) "u" ["a", "b", "c", "d", "e"]
"abcdeu"
于 2013-01-24T22:26:54.153 回答
3

干得好，你自己发现foldr的！（我希望这听起来不是嘲讽之类的，这不是那个意思；大多数人都觉得褶皱不自然，并且必须非常努力地思考才能理解它！）

我建议你处理这些情况的方法是尝试自己编写你想要的函数，并找出类型，然后在Hoogle中搜索该类型以查看是否已经存在这样的函数。

在这种情况下，您可以尝试以这种方式编写函数。我们称之为foo：

-- If we see an empty list the result should be u
foo u f [] = u
-- If we're given a a non-empty list we recurse down the list to get a partial 
-- result, then "add on" to it:
foo u f (x:xs) = f x (foo u f xs)

一旦你定义了这个函数，你可以加载它ghci并使用它的:t命令来找到它的类型：

*Main> :load "../src/scratch.hs"
[1 of 1] Compiling Main             ( ../src/scratch.hs, interpreted )
Ok, modules loaded: Main.
*Main> :t foo
foo :: t1 -> (t -> t1 -> t1) -> [t] -> t1

现在我们可以在 Hoogle 中搜索 typet1 -> (t -> t1 -> t1) -> [t] -> t1。最上面的结果是foldr，它的类型是(a -> b -> b) -> b -> [a] -> b- 相同，foo但变量重命名并且参数顺序颠倒了。搜索结果还告诉我们该函数在Prelude模块中——Haskell 默认加载的模块。您可以单击结果以在文档中找到其定义，该文档使用以下等式对其进行了描述：

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

他们将该f函数用作中缀运算符，我希望这不会让您感到困惑，但以防万一我们可以将其重写为：

foldr f z [x1, x2, ..., xn] == f x1 (f x2 ... (f xn z) ...)

这正是您想要的行为。

为什么我在foldr上面做了这么大的事情？因为foldr实际上是拆分列表的最基本功能。以这种方式查看类型：

foldr :: (a -> b -> b)  -- ^ What to do with a list node
      -> b              -- ^ What to do with the empty list
      -> [a]            -- ^ A list
      -> b              -- ^ The final result of "taking the list apart."

事实证明，很多列表函数可以很容易地写成foldr：

map f = foldr step []
    where step x rest = (f x):rest

-- | Append two lists
xs (++) ys = foldr (:) ys xs

-- | Filter a list, keeping only elements that satisfy the predicate.
filter pred = foldr step []
    where step x rest | pred x    = x:rest
                      | otherwise = rest

-- | Find the first element of a list that satisfies the predicate.
find pred = foldr step Nothing
    where step x r | pred x    = Just x
                   | otherwise = r
于 2013-01-26T00:40:46.250 回答
2

右折看起来不错。

foo :: (a -> b -> b) -> b -> [a] -> b
foo f u xs = foldr (\x acc -> f x acc) u xs

我发现在学习一门语言时，人们经常会问“有没有更简单的方法可以做到这一点？” 答案几乎总是肯定的。

于 2013-01-24T22:27:43.473 回答