實現需要用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

回答

相關問題