Haskell中的排列實現

Question

我試圖在Haskell中實現一個列表的排列。排列的想法是這樣的：

基本情況是當列表長度爲0和1時，它是列表本身，當大小爲2時，排列給出列表本身以及交換元素。

現在，給出一個列表[a，b，c，d]我們排列[b，c，d]並附加一個。並且我們改變我們的列表，使其在第一個b中像[b，a，c，d]和遞歸地排列[a，c，d]等等。

到目前爲止，我在Haskell中完成了以下代碼。這完美的作品。但我對這包含的'haskell-ness'的級別不滿意。我想提供一些關於如何在Haskell中更加可讀和高效的提示。提前致謝。代碼如下：

-- swap the first element of a list with the element at the index 
swapFirstWith index l | index == 0 = l 
         | otherwise = [l!!index] 
         ++ (take (index-1) (tail l)) 
         ++ [head l] 
         ++ (drop (index+1) l) 


permutations :: [a] -> [[a]] 
permutations [] = [[]] 
permutations [a] = [[a]] 
permutations [a,b] = [[a,b], [b,a]] 
permutations lst = foldl (++) [] (map (\x-> miniperms x) swappedList) 
    where miniperms l = map (\x-> (head l): x) $ permutations (tail l) 
      swappedList = map (\(i, x) -> swapFirstWith i lst) (zip [0..] lst) 


main = do 
    putStrLn $ show $ perms 
    putStrLn $ show $ length perms 
    where lst = [1,2,3,4,5,6,7,8,9] 
      perms = permutations lst 

Answer 1

避免!!,head,tail有利於模式匹配。這些功能是部分的，並且可能會在列表太短時導致程序崩潰。模式匹配（詳盡時）沒有這樣的問題。

length, take, drop往往最好留下未使用。

相反，讓我們考慮簡單的遞歸：

perms :: [a] -> [[a]] 
perms []  = [[]] 
perms (x:xs) = doSomething x (perms xs) 

如何把perms xs成perms (x:xs)？在xs的每個置換p中，我們需要在p的任何可能點插入x。我們得到

perms :: [a] -> [[a]] 
perms []  = [[]] 
perms (x:xs) = [ p' | p <- perms xs, (use insert here) ] 

，其中在所有點插入完成如下

insert :: a -> [a] -> [[a]] 
insert x [] = [[x]] 
insert x (y:ys) = ... -- todo 

我將離開你來完成代碼。

Answer 2

隨着

picks :: [t] -> [([t], t)] 
picks [] = [] 
-- picks [x] = [([],x)] 
picks (x:xs) = [(xs,x)] ++ [(x:ys,y) | (ys,y) <- picks xs] 

是，直截了當，

perms :: [t] -> [[t]] 
perms [] = [[]] 
perms xs =   -- [(x:zs) | (ys,x) <- picks xs, zs <- perms ys] 
    do      
    (ys,x) <- picks xs  -- pick an element, any element 
    zs  <- perms ys  -- permute what's left 
    return (x:zs)    -- and put them together  

---

編輯：創建和繞過更新域的重複模式表明，我們可以做的更好，即使其成爲正確的域名後自動傳遞給我們，作爲此特定計算模型的一部分「管線」，就像它一樣。

現在我們不得不擔心出現錯誤，明確指定臨時域名，並且要特別小心地傳遞正確的變量作爲要使用的域名。自動爲我們處理這些擔憂是很好的。

具體的notions of computation被捕獲到一個Monad類型的特定實例。

隨着"unique selection" monad由Louis Wasserman答案的幫助下，

newtype UniqueSel t a = UniqueSel {runUS :: [t] -> [ ([t], a) ] } 
--          domain updated_dom, result 
instance Functor (UniqueSel t) where 
    fmap = liftM 
instance Applicative (UniqueSel t) where 
    pure a = UniqueSel (\ choices -> [(choices, a)]) -- unchanged domain 
    (<*>) = ap 
instance Monad (UniqueSel t) where 
    return = pure 
    m >>= k = UniqueSel (\ choices -> [ r | (cs, a) <- runUS m choices, 
              r  <- runUS (k a) cs ]) 

我們可以重新寫上面基於列表的do代碼UniqueSel基礎的do代碼，

perm = do { x <- UniqueSel picks ; xs <- perm ; return (x:xs) } 

其中所有臨時域跟蹤變量都剛剛消失！我們在這裏所做的事情的性質變得更加清晰和明顯。沒有分心了。

這最後的代碼片斷雖然不會工作，因爲我們不警惕從空域，這將發生，將有效地中止所有的計算，生產只是[]最終作出選擇。我們需要返回和[]作爲空域的結果，我們自己。

我們可以在我們的小唯一-選擇計算引入新「原始」行動語言，把隱藏的選擇到我們宇宙，用choices = UniqueSel (\cs -> [(cs, cs)]);並在空域分支，像

perm = do { cs <- choices ; if (null cs) then return [] else 
      do { x <- UniqueSel picks ; xs <- perm ; return (x:xs) } } 

並運行此計算描述，我們已經建立，通過使用perms = map snd . runUS perm;但是在模塊Control.Monad中的標準庫中已經爲我們捕獲了此模式，作爲函數sequence;所以我們可以定義爲

perms :: [t] -> [[t]] 
perms = map snd . (runUS =<< sequence . (UniqueSel picks <$)) 

-- perms xs = map snd $ runUs (sequence [UniqueSel picks | _ <- xs]) xs 
--   = .....   (replicateM (length xs) (UniqueSel picks)) xs 

這將通過與輸入相同長度的選取序列來運行輸入。

事實上，爲了排列n-長長的列表是從可能的選擇不斷縮小的池中任意選擇n。