haskell - 定义一个函数，将给定列表的所有可能排列返回为对列表

Question

我是 Haskell 新手，有人给我一个工作表问题，这让我很困惑。问题是要求我定义一个函数，它接受一个元组列表，每个元组包含一个数字子列表并返回一个元组列表，每个元组包含一对整数。 这是预期的输入和输出。

possibles [([1],[2,3,4]),([1,2],[3,4])] ===> [(1,234),(1,243),(1,342),(1,324),(1,423),(1,432),(12,34),(12,43),(21,34),(21,43)]

我正在尝试使用“Data.List”库中的“permutations”函数以及我在下面制作并附加的另外两个函数。

-- takes a list of digits and returns the positive integer formed from those digits, so that number [9,1,2,4] ==⇒ 9124

number :: [Int] -> Int
number digits = foldl (\acc x -> acc * 10 + x) 0 digits

-- returns all of the non-trivial splits of a list as a list of pairs, so that splits [1,2,3,4,5] ⇒ [([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]

splits :: [Int] -> [([Int], [Int])]
splits [] = []
splits [x] = []
splits (x : xs) = ([x], xs) : map f (splits xs)
  where
    f (z, y) = (x : z, y)

Answer 1

欢迎加入 Haskell 大家庭!这是一个有趣的问题，可以帮助您发现 Haskell 的美妙之处。

首先，让我们先看看问题，然后再进行实现:

1. 将 [2,3,4] 转换为 [[2,3,4], [2,4,3], [3,2,4], [3, 4,2], [4,2,4], [4,3,2]]
2. 将 [2,3,4] 转换为 234(您已经实现了这部分)
3. 将 ([12,21], [34,43]) 转换为 [(12,34),(12,43),(21,34),(21, 43)]
4. 将所有内容组合在一起(组合真的很强大)
5. 重构

其次，我推荐两个有用的工具:

• https://replit.com/languages/haskell - 在线 Haskell REPL 快速测试代码
• https://hoogle.haskell.org/ - 搜索可用的Haskell函数，如果想了解实现就研究源代码

现在让我们尝试实现这一点。

首先，我们知道输入类型是[([Int], [Int])]:

-- try out at https://replit.com/languages/haskell 

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

main = print input  

现在让我们按照上面提到的步骤进行操作。

第 1 步称为排列::[a] -> [[a]]，它不仅适用于 Int，还适用于任何类型。

如果你在hoogle中搜索[a] -> [[a]]，你可能会找到this function ，现在回到 REPL:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

main = print $ step1 [2,3,4]
-- result: [[2,3,4],[3,2,4],[4,3,2],[3,4,2],[4,2,3],[2,4,3]]

对于第 2 步，我们现在使用您的代码:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits
-- or try the shorter version
-- step2 = foldl (\acc x -> acc * 10 + x) 0

main = print $ step2 [2,3,4]
-- result: 234

第 3 步是使用 list comprehension 的一个很好的示例:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits

step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]

main = print $ step3 ([12,21], [34,43]) 
-- result: [(12,34),(12,43),(21,34),(21,43)]

现在是令人兴奋的部分 - 构图。 首先我们结合step1和step2:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits

step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]

step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1
    

main = print $ step12 [2, 3, 4]
-- result: [234,324,432,342,423,243]

请注意，您可以专注于函数组合而不关心此处的值:

step12 :: [Int] -> [Int]
step12 = map step2 . step1

现在我们将step3与step12结合起来

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits

step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]

step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1

step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)


main = print $ step123 ([1,2],[3,4])
-- result: [(12,34),(12,43),(21,34),(21,43)]

现在最后一步是一个简单的map或fmap(如果你愿意的话)。

让我们看看到目前为止我们得到了什么:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits

step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]

step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1

step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)


main = print $ map step123 input
-- result: [[(1,234),(1,324),(1,432),(1,342),(1,423),(1,243)],[(12,34),(12,43),(21,34),(21,43)]]

现在我们通过(map step123 input)得到[[(Int, Int)]]，我们需要做的就是一个将[ [a]] 到 [a] 中，我们在 hoogle 中搜索一下(注意选择行为正确的那个)。好的，我们找到了concat .

所以让我们将step4放在这里来完成我们的第一个版本的解决方案:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations

step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 + x) 0 digits

step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]

step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1

step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)

step4 :: [([Int], [Int])] -> [(Int, Int)]
step4 x = concat (map step123 x)
-- step4 = concat . map step123
-- step4 = concatMap step123

main = print $ step4 input
-- result: [(1,234),(1,324),(1,432),(1,342),(1,423),(1,243),(12,34),(12,43),(21,34),(21,43)]

请再次注意，我们可以专注于组合而不考虑值:

step4 :: [([Int], [Int])] -> [(Int, Int)]
step4 = concat . map step123
-- alternatively
-- step4 = concatMap step123

现在让我们看看如何使用列表理解重构 step123 并将其重命名为 getCombinations 之类的名称:

import Data.List (permutations)

input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]

toNumber :: [Int] -> Int
toNumber = foldl1 (\x y -> 10*x+y)

-- ([1, 2], [3, 4]) -> [(12, 34), (12, 43), (21, 34), (21, 43)]
getCombinations :: ([Int], [Int]) -> [(Int, Int)]
getCombinations (xs, ys) = [
  (toNumber x, toNumber y) 
  | x <- permutations xs
  , y <- permutations ys]

handleInput :: [([Int], [Int])] -> [(Int, Int)]
handleInput = concatMap getCombinations

main = print . handleInput $ input

这绝不是最简洁或最高效的代码，但它是一个好的开始，我希望您能从中学到一些东西。

你有一个良好的开始，继续努力并享受 Haskell :)