列表连接使用与foldl“ foldr相似

我现在学习Haskell，我面临着以下问题：列表连接使用与foldl“ foldr相似

我想用与foldl重写++函数”和foldr相似。我用foldr完成它：

myConcat xs ys = foldr (:) ys xs

我不能用foldl'来做。我读过RealWorldHaskell，foldr对于做这种事情很有用。好吧，但我不能用foldl写一个等价物给++吗？有人可以告诉我我该如何做到这一点（如果可以做...本书没有提及任何有关它的）...

Haskell的类型机制是否阻止我这样做？每次我尝试时，我得到一个类型错误...

来源

2011-06-17 Adi

我猜，你得到的是从尝试到foldr到foldl'简单地切换错误：

myConcat xs ys = foldl' (:) ys xs

产生的误差（用我的拥抱REPL）：

ERROR - Type error in application 
*** Expression  : foldl' (:) xs ys 
*** Term   : (:) 
*** Type   : a -> [a] -> [a] 
*** Does not match : [a] -> a -> [a]

在公告最后两行（提供的类型和预期类型）[a]和a的位置处于相反的位置。这意味着我们需要一个类似于(:)的函数，但它以相反的顺序参数。

Haskell有一个功能，它为我们做到这一点：flip函数。基本上，flip相当于

flip :: (a -> b -> c) -> (b -> a -> c) 
flip f y x = f x y

即，flip取二进制函数作为参数，并返回原来的另一个二进制函数，其自变量被反转（“翻转”）。因此，尽管(:)的类型为a -> [a] -> [a]，但我们看到flip (:)的类型为[a] -> a -> [a]，因此它是foldl'的参数的完美候选者。

使用flip，我们现在有这样的代码：

myConcat xs ys = foldl' (flip (:)) ys xs

此结果与事实foldl'的类型是(a -> b -> c) -> a -> [b] -> c

带参数运行此[1..5]和[6..10]，我们得到的[5,4,3,2,1,6,7,8,9,10]结果，这几乎是我们想要的。唯一的问题是结果中第一个列表倒退。添加一个简单的调用reverse赋予我们的myConcat最后定义：

myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

纵观这一过程显示了经常出现的好东西之一，当写Haskell代码：当你碰到一个问题，您可以一次解决一个（小）步骤。当你已经有一个工作实现时，这是尤其如此，而你只是试图编写另一个实现。需要注意的是，如果您更改了实现的一部分（在这种情况下，将foldr更改为foldl'），那么其他许多其他必需的更改就会脱离类型定义。剩下的少数是可以很容易找到的纠正问题，无论是通过运行测试用例，还是通过查看所使用函数的确切性质。 PS：任何可以清理最后一行代码的Haskell家伙，都可以随时这样做。虽然它并不可怕，但我不觉得它很漂亮。不幸的是，我对Haskell不太了解。

来源

2011-06-17 05:10:48

您的帖子真实我帮助了我。感谢您的解释:) – Adi 2011-06-17 12:54:07

data [] a = ... | a : [a] 
(:) :: a -> [a] -> [a]

（:) op对待左，右操作数不同。

a :: Char 
b :: Char 
c :: [Char]

a:[b]是确定

a:b是不正常

a:c是确定的。

寻找类型签名foldr (:)和foldl (:)你会发现他们的不同。

来源

2011-06-17 04:07:38 Nybble

:运算符将一个单个元素（其左参数）连接到列表及其正确参数。

foldl到的参数，

折叠功能
初始值
值的列表到步骤通过。

回想特别是折叠函数采用，因为它的左边参数，电流值，它开始作为初始值。因此，折叠函数的左参数是一个列表，它的正确参数是单个值。如果你玩它，你可以[仅通过切换参数使类型匹配]得到的东西一样，

> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6] 
[6,5,4,1,2,3]

但是，这是不是你想要的。你必须自己解决它;我可以使用foldl构建一个反向函数，并将其作为子程序调用 - 但如果可以，请随意以不同的方式解决它。

来源

2011-06-17 04:55:56 gatoatigrado

你的解决方案是优雅的:)谢谢你的帮助我理解 – Adi 2011-06-17 12:55:29

你可以做到这一点使用与foldl但相比使用与foldl来FOLDR根据实施

的例子，不会是有效的：

show $ (\xs ys -> foldl (\s e -> e:s) ys (reverse xs)) [1,2] [3,4]

来源

2011-06-17 05:23:07 Ankur

为什么foldr更有效率？ – 2015-05-12 04:41:46

它并不总是可能的，因为foldr（以及++）在无限列表上工作，但foldl不。然而，foldl可以来编写foldr方面：http://www.haskell.org/haskellwiki/Foldl_as_foldr

更新：对于有限名单，foldr可以也写在条款foldl：

foldr :: (b -> a -> a) -> a -> [b] -> a 
foldr f a bs = 
    foldl (\g b x -> g (f b x)) id bs a

所以从这一点就可以实现(++)在foldl

来源

2011-06-17 06:31:51 newacct

列表连接使用与foldl“ foldr相似

回答

相关问题