功能非常有限的 Haskell 排列

Question

我必须在 haskell 中实现一个接受列表 [Int] 的函数并给出一个列表 [[Int]]具有所有排列，但我只允许使用: [] , : , True , False ，比较，&& , || ，和not

permutations [] = [[]]
permutations xs = [(y:zs) | (y,ys) <- picks xs, zs <- permutations ys]
   where
   picks (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- picks xs]

我的想法是使用类似的东西，但我必须替换 <-

Answer 1

正如 chepner 在评论中提到的，一些缺失的基本库函数可以很容易地“当场”重新实现。

Wikipedia article on permutations除其他事项外，我们还发现 Steinhaus–Johnson–Trotter algorithm ，这似乎非常适合链接列表。

对于这个算法，一个基本的构建 block 是我们可以声明为的函数:

spread :: a -> [a] -> [[a]]

例如，表达式 spread 4 [1,2,3] 必须将 4 放置在 [1,2;3] 内的所有可能位置，因此计算结果为:[[4 ,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]。要获得 [1,2,3,4] 的所有排列，只需将 spread 4 应用于 [1,2,3] 的所有排列。以递归方式编写 spread 很容易:

spread :: a -> [a] -> [[a]]
spread x [] = [[x]]
spread x (y:ys) = (x:y:ys) : (map (y:) (spread x ys))

排列可以这样获得:

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concat (map (spread x) (permutations xs))

总体而言，符合规则的源代码版本将如下所示，具有自己的本地版本的 map 和 concat Prelude 函数:

permutations :: [a] -> [[a]]
permutations  []     =  [[]]
permutations (x:xs)  =  myConcat (myMap (spread x) (permutations xs))
  where
    myMap fn  []     =  []
    myMap fn (z:zs)  =  (fn z) : (myMap fn zs)

    myConcat   []          =  []
    myConcat ([]:zss)      =  myConcat zss
    myConcat ((z:zs):zss)  =  z : (myConcat (zs:zss))

    spread z []      =  [[z]]
    spread z (y:ys)  =  ( z:y:ys) : (myMap (y:) (spread z ys))