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。