Haskell中的排列实现

2018-06-08 00:02:49

我试图在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

避免!!,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

我会离开你去完成代码。

同

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

编辑：创建和传递更新域的重复模式表明我们可以做得更好，也就是说，让正确的域自动在幕后传递给我们，作为这个特定计算模型的“管道”的一部分，照原样。

现在我们不得不担心出现错误，明确指定临时域名，并且要特别小心地传递正确的变量作为要使用的域名。自动为我们处理这些担忧是很好的。

使用Monad类型类的特定实例捕获具体的计算概念。

在Louis Wasserman的回答中的“独特选择”monad的帮助下，

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运行我们构建的计算描述perms = map snd . runUS perm 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从可能的选择不断缩小池任意选择。

链接地址: http://www.djcxy.com/p/24325.html

上一篇: Permutation implementation in Haskell

下一篇: Is there a better way to create permutations of string w bounded by length?