实现需要用foldr

这是使用foldr我take版本：实现需要用foldr

myTake n list = foldr step [] list 
       where step x y | (length y) < n = x : y 
           | otherwise = y 

main = do print $ myTake 2 [1,2,3,4]

输出是不是我所期望：

[3,4]

我又试图通过插入y长度为本身调试其结果是：

[3,2,1,0]

我不明白为什么长度按降序排列。也许我错过了一些明显的东西？

来源

2013-04-08 badmaash

或在口头上，原因是'y'在'一步xy'被称为'foldr'代表** **不为*“列表的其余尚待已处理“*，**但**为*”处理列表的其余部分的结果“*。所以你的函数说：*“如果已处理的列表剩余长度已经是'n'或更多，请不要在其中加上任何内容，否则在当前元素前添加”*。 – 2013-06-22 20:05:23

如果要使用foldr执行take，则需要模拟从左向右遍历列表。重点是让折叠函数依赖于一个额外的参数，它编码你想要的逻辑，而不仅仅依赖于列表的折叠尾部。

take :: Int -> [a] -> [a] 
take n xs = foldr step (const []) xs n 
    where 
    step x g 0 = [] 
    step x g n = x:g (n-1)

这里，foldr返回一个函数，它接受一个数字参数和遍历从左至右从它所需要的量服用列表。由于懒惰，这也适用于无限名单。一旦额外的参数达到零，foldr将短路并返回一个空列表。

来源

2013-04-08 13:59:08 is7s

Visualization of <code>foldr</code>

foldr将应用从*最后的元素在启动功能step **。也就是说，

foldr step [] [1,2,3,4] == 1 `step` (2 `step` (3 `step` (4 `step` []))) 
         == 1 `step` (2 `step` (3 `step` (4:[]))) 
         == 1 `step` (2 `step (3:4:[])) -- length y == 2 here 
         == 1 `step` (3:4:[]) 
         == 3:4:[] 
         == [3, 4]

长度被以递减顺序，因为:是前面加上操作“插入”。较长的长度被添加到列表的开头。

_{（从http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29拍摄的图像）}

*：为了简单起见，我们假设每一个操作都严格，这是OP的step实现真实的。

来源

2013-04-08 13:20:03 kennytm

“'foldr'将应用从*最后一个元素*开始的'step'函数。”这种说法在懒惰评估面前充其量是非常误导的。 Haskell实际上是从左到右评估你的第二棵树，如果step函数对它的第二个参数不是严格的，它可能会提早中止计算。最简单的例子是'safeHead = foldr（\ x _ - > Just x）Nothing'。 – 2013-04-08 17:22:52

我应该补充说明你的评估步骤顺序是从内部函数应用程序到外部函数应用程序，这与Haskell的做法相反。最外面的'step'首先被评估，其中'1'作为第一个参数。如果'step'不需要它的第二个参数，那么计算就在那里结束，然后再查看列表元素的其余部分。如果'step x _ = Just x'，那么'foldr step Nothing [1,2,3,4] == step 1（foldr step Nothing [2,3,4]）==只是1'。 – 2013-04-08 17:36:41

@sacundim但是这个问题的'step'在第二个参数中是严格的，所以在这种情况下'foldr'别无选择，只能从列表的最后到最前面，并且评估最外面的'step'，首先必须对内部的“步骤”进行评估。答案会从明确表示这是一种特殊情况中受益，但对于给定的代码，描述是正确的。 – 2013-04-08 19:11:06

到目前为止的其他答案让它变得太复杂了，因为它们似乎过分坚持foldr“从右到左”的概念。有一种感觉，但Haskell是一种懒惰的语言，所以使用懒惰折叠步骤的“从右到左”计算实际上将从左到右执行，因为结果已被消耗。

研究验证码：

take :: Int -> [a] -> [a] 
take n xs = foldr step [] (tagFrom 1 xs) 
    where step (a, i) rest 
       | i > n  = [] 
       | otherwise = a:rest 

tagFrom :: Enum i => i -> [a] -> [(a, i)] 
tagFrom i xs = zip xs [i..]

来源

2013-04-08 17:18:57

实现需要用foldr

回答

相关问题