picks :: [a] -> [(a, [a])]。
picks [] = [] 。
picks (x:xs) = (x,xs) : [(y,x:ys)| (y,ys) <- picks xs]
picks [1.4] = [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4])]/code>
這個Haskell函式作業得很好，但是為什么呢？串列中的前兩個圖元是很明顯的，但是其余的是如何建立的，這讓我的大腦很崩潰。
uj5u.com熱心網友回復：
picks是做什么的？它回傳從串列中選擇一個元素的所有可能的方法，以一個元組的形式(choice, rest)，其中choice是你選擇的專案，rest是你沒有選擇的元素。請注意，[choice] rest總是包含與原始串列相同的元素，盡管順序不一定相同。
那么，picks是如何作業的？當引數為空時，很簡單：沒有辦法選擇一個元素，所以我們回傳空串列。
picks [] = [] 。
當引數是非空時，我們可以做兩件事中的一件。要么x是元組的第一個元素，要么它是第二個元素的一部分。最簡單的做法是選擇第一個元素；我們用(x:xs)來解壓串列，并產生(x, xs)。
picks (x:xs) = (x, xs) : ?
我們可以做的另一件事是不挑選x，而是從xs挑選一個元素。如何從xs中選擇一個元素呢？我們使用picks! 這一次，picks回傳一個圖元的串列，其中x既不是第一個元素也不是第二個元素的成員。我們只需將(x, xs)與這個串列結合起來。
-- x != y, x `elem` ys == False
picks (x:xs) = (x, xs) : [ (y, ?) | (y, ys) <-pick xs]
但是x 確實需要成為第二個元素的成員，因為它不是第一個元素。所以我們必須把它放回去。最簡單的地方是在每一種情況下，把它放在ys的開頭：
picks (x:xs) = (x, xs) : [ (y, x:ys) | (y, ys) <- picks xs]
uj5u.com熱心網友回復：
在很多情況下，手動展開運算式是有幫助的：
picks [1. 4] = (1, [2..4]) 。[(y, 1:ys) | (y, ys) <- picks [2...4] ]
--繼續挑選[2...4]/span>。
挑選 [2...4] = (2, [3.4] ) : [(y, 2:ys) | (y, ys) <- picks [3...4] ]
--繼續挑選[3...4]/span>。
挑選 [3, 4] = (3, [4] ) 。[(y, 3:ys) | (y, ys) <- picks [4] ]
--繼續挑選[4]。
精選[4] = (4, []) : [(y, 4: ys) | (y, ys) <- 精選[] ]
= (4, []) : [(y, 4: ys) | (y, ys) <- []]
= (4, []) : [] 。
= [(4, [])] 。
picks [3, 4] = (3, [4] ) : [(y, 3:ys) | (y, ys) <- [(4, [])].
= (3, [4]) : [(4, 3:[] ] ]
= (3, [4]) : [(4, [3])
= [(3, [4]), (4, [3]) ]
--等一個。
uj5u.com熱心網友回復：
遞回情況將回傳一個串列，其中第一項(x, xs)回傳一個2元組，作為第一項（我們挑選的專案）x，其余專案是我們在串列尾部做的picks，并在所有這些專案前加上x。
如果我們在一個單子串列上運行這個程式，例如[1]，我們就可以得到如下選項：
picks [1] = (1, [ ] ) : [(y, 1: ys) | (y,ys) <- picks []]/code>由于picks []等同于[]，因此，這意味著我們檢索到：
picks [1] = (1, [] ) : [(y, 1: ys) | (y,ys) <- []]/code>因此，串列理解將產生一個空串列，因此，picks [1]的結果是：
picks [1] = [（1, [] ）]
如果我們現在處理有兩個元素的串列，遞回呼叫將回傳一個有一個元素的串列：尾部的唯一元素和一個空串列。
這就意味著，如果我們在picks上運行picks [1,2]，我們就會得到：
picks [1, 2] = (1, [2] ) : [(y, 1:ys) | (y,ys) <- 挑選[2]]由于picks [2]回傳[(2, [])]，因此我們將在(2, [])元組中的空串列前綴為1，因此我們得到：
picks [1, 2] = (1, [2] ) : [(y, 1:ys) | (y,ys) <- [(2, [])].
= (1, [2]) : [(2, [1])
= [(1, [2]), (2, [1]) ]串列理解中的x:ys部分將預置串列的頭部，所以1到由picks [2]回傳的串列。由于是沒有被遞回呼叫選中（我們在專案的尾部遞回呼叫picks），因此我們需要在串列的某個地方插入它，而最簡單的方法是預置它。
如果我們這樣處理三個專案，我們將檢索到的資料是：
picks [1, 2, 3] = (1, [2, 3] ) 。[(y, 1:ys) | (y,ys) <- picks [2, 3] ]
= (1, [2]) : [(y, 1: ys) | (y,ys) <- [(2, [3]), (3, [2])] ]
= (1, [2]) 。[(2, [1, 3]) 。(3, [1, 2])].
= [(1, [2]), (2, [1, 3]), (3, [1, 2]) ]
因此，對于有三個以上專案的串列，每次遞回都會把肯定沒有被picks xs的遞回尾部選中的專案預置，并把沒有被選中的專案串列預置為x。
uj5u.com熱心網友回復：
在這種情況下，使用高階函式的演算法表述實際上比基于串列理解的演算法看起來更清晰：
picks [] = [] 。
picks (x:xs) = -- (x,xs) : [(y, x:ys) | (y,ys) <- picks xs]/span>
(x,xs) : map (second (x:)) (picks xs)
如果你不明白什么是second (x:)，你可以把它讀成一個偽代碼：它把(x:)應用到一對的第二部分，所以second (x:) (a,b) = (a, x:b) 。而map對其引數串列中的每一個元素(map的第二個引數)都是如此。
因此，我們有了，從頭開始建立我們的理解：
picks (1:[] ) =
-- picks (x:xs) = (x,xs) : map (second (x:) ) (picks xs)
= (1,[]) : map (second (1: )) (picks [])
= (1,[]) : map (second (1: )) []
= (1,[]) : []
= [(1,[])] 。
picks [2,1] = picks (2:[1] )
= (2,[1] ) : map (second (2:) (picks [1] )
= (2,[1]) : map (second (2:)) [（1, [] ）]
= (2,[1]) : [(1,[2])
= [(2,[1]) , (1,[2]) ]
picks [3,2, 1] =
= (3,[2,1] ) : map (second (3:)) (picks [2,1] )
= (3,[2,1]) : map ( second (3: )) [(2, [1]) , (1, [2]) ]
= [(3,[2,1]) , (2, [3,1]) , (1,[3,2] ]
picks [4,3,2, 1] =
= (4,[3,2,1]) : map ( second (4: )) [(3,[2,1]) , (2, [3,1]) , (1,[3,2]) ]
= [(4,[3,2,1]) 。 (3,[4,2,1] ) 。(2,[4,3,1] ) 。(1,[4,3,2]) ]
picks [5,4,3,2,1] =
= [([5,[4, 3, 2,1]），（4, [5,3,2。 1]), (3,[5, 4,2,1] ）。) (2,[5,4,3, 1]), (1,[5, 4,3,2]）]
....
為了更好地看清模式，把它們放在一起，結果是：
。
picks [ ] = [ ]
picks [ 1] = [ (1,[ ] )]
picks [ 2,1] = [ （2, [1]) , (1,[ 2])]
picks [ 3,2, 1] = [ (3,[ 2, 1] , (2, [ 3, 1] , (1,[ 3,2] )]
picks [ 4,3, 2,1] = [ (4, [3,2,1]) ，（3, [4,2,1]) , (2,[ 4, 3,1]) , (1, [4,3,2]) ]
picks [5,4,3,2,1] =
= [([5,[4, 3, 2,1]），（4, [5,3,2, 1]) , (3,[5, 4,2,1] ） 。(2,[5,4,3, 1]) , (1,[5, 4,3,2]）]
....
于是picks產生了所有挑選一個元素的方法，在該元素被移除后，將其與串列中的其余元素配對。
顯然，對于長度為0（空）的串列情況，[]，以及長度為1（單子）的情況[]和長度為2的情況[2,1]都是如此。并且如果它對長度為n的串列是這樣做的，那么對于n 1我們知道它也是正確的，因為它從第一個選取開始，然后map在為n情況產生的結果中把第一個元素加入每個剩余部分。這是正確的.
是的，你可以把它理解為"n的情況是正確的 "和 "因此，n 1是正確的"。因此（并考慮到0情況的正確性）通過歸納原則，結果對任何 n都是正確的。也就是說，對于所有的人來說。是的，它們有無限多，但每個n本身都是有限的。
如果起點是正確的，并且每一步都是正確的，那么整個旅程也一定是正確的。我們不需要理解它到底是如何對n情況做什么的，展開所有的遞回層。這很難。相反，我們要證明歸納的步驟是正確的，基礎案例是正確的，就這樣。
在試圖理解遞回函式到底是如何做的程序中，最重要的三條規則是：
我們可以解決這兩個缺陷。
我們可以通過
來同時解決這兩個缺陷。picks3 :: [a] -> [([a], a, [a])] 。
picks3 [] = []
picks3 (x:xs) = go [（[],x,xs）] xs
where
go acc [] = reverse acc
go acc@((a,b,_):_) (x:xs) = go ((b:a,x,xs):acc) xs
這樣，
> picks3 [1.4]
[([],1,[2,3,4] )。 ([1],2,[3,4]) 。 ([2,1],3,[4]) 。 ([3,2,1],4,[] )]
現在這個是線性的，如果我們選擇并愿意付出代價，很容易從中產生picks的輸出。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/316926.html
標籤：
上一篇：移除串列中第一個出現的元素