haskell - 使用 Haskell 根据等效总和对子列表值进行分组

Question

我正在尝试学习 Haskell，并且我正在尝试创建一个函数，该函数采用列表列表并按等价总和对子列表进行分组。这不是家庭作业。

import Data.List
let x = [[1,2],[2,1],[5,0],[0,3],[1,9]]
let groups = groupBy (\i j -> sum i == sum j) x

我在 GHCi 中得到这个输出:

[[[1,2],[2,1]],[[5,0]],[[0,3]],[[1,9]]]

我收到 [[1,2],[2,1]]分组在一起，但不与 [0,3] .为什么是这样？

我怀疑我需要使用 map ，但我似乎无法让它发挥作用。

Answer 1

groupBy 函数保留输入顺序，因此是可逆的。如果你愿意扔掉这些信息，你可以使用以下代码

import Data.List (foldl')
import Data.Map (elems,empty,insertWith')

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

在行动:

*Main> bucketBy sum x[[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]]

---

How it works

The application of elems from Data.Map gives a clue for what’s happening.

elems :: Map κ α -> [α]

O(n). Return all elements of the map in the ascending order of their keys.

elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []

Mapping

A Map associates values of some type κ with values of another possibly distinct type α. In the example from your question, you start with x whose type is

*Main> :type xx :: [[Integer]]

That is, x is a list of integer lists. The type of the resulting partition of x you want is

*Main> :t [[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]][[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]] :: Num τ => [[[τ]]]

or a list of lists where each of the latter lists are themselves lists that all have the same sum. The Num τ => bit is a context that constrains the type τ to be an instance of the typeclass Num. Happy for us, Integer is such a type:

*Main> :info Integerdata Integer…instance Num Integer -- Defined in GHC.Num…

We know then that the type of the partition is [[[Integer]]]. This typeclass nonsense may seem unnecessarily fussy, but we’ll need the concept again in just a moment. (To give you an idea of what’s going on, the typechecker doesn’t have enough information to decide whether the literal 0, for example, is of type Int or Integer.)

Each sublist contains lists with the same sum. In other words, there exists a mapping from a sum to a list of integer lists. Therefore, the type of the Map used in bucketBy must resemble

Map Integer [[Integer]]

例如，与总和 3 相关联的列表

[ [0,3]
, [2,1]
, [1,2]
]

折叠递归模式

折叠是一种非常普遍的模式。左折， foldl Haskell 中的和friends 允许你在列表的元素之间“插入”一个运算符，从列表左端的零值开始。例如， [5,3,9,1] 的总和表示为左折叠是

((((0 + 5) + 3) + 9) + 1)

或者

foldl (+) 0 [5,3,9,1]

也就是说，从基值零开始，我们连续添加列表的元素并累加总和。

回想一下 bucketBy 的定义包含

elems . foldl' go empty

这意味着左折叠的结果必须是 Map Integer [[Integer]] 类型，我们折叠的零值是该类型的空 Map，和 go以某种方式将列表的每个连续值添加到 map 中。

请注意 foldl'是 foldl 的严格表亲，但严格性超出了这个答案的范围。 (另见 “Stack overflow” on HaskellWiki。)

伙计，我的 list 在哪里？

鉴于 foldl' 的类型

*Main> :t foldl'foldl' :: (a -> b -> a) -> a -> [b] -> a

we should have three arguments in the application, but only two are present in the code above. This is because the code is written in point-free style. Your list is there implicitly due to partial application of foldl'.

Think back to the sum-as-fold example above. The type of that application without the final argument is

*Main> :t foldl (+) 0foldl (+) 0 :: Num b => [b] -> b

Partial application allows us to create new functions. Here we defined a function that computes a number from some list of numbers. Hmm, sounds familiar.

*Main> :t sumsum :: Num a => [a] -> a

The . combinator expresses function composition. Its name is chosen to resemble the notation g∘f as commonly seen in mathematics textbooks to mean “do f first and then compute g from the result.” This is exactly what’s happening in the definition of bucketBy: fold the list of values into a Map and then get the values of out the Map.

If ya gotta go, go with a smile

In your comment, you asked about the purpose of m. With an explicit type annotation, we might define go as

...
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

匹配变量与类型， m是我们目前积累的Map， l是下一个 Integer我们想要扔到适当的桶中的列表。回想一下 eq是外部 bucketBy 的参数.

我们可以使用 insertWith' 控制新项目如何进入 map 。 . (按照惯例，名称以尾随引号结尾的函数是严格的变体。)

(++) 组合器附加列表。申请 eq l为 l 确定合适的存储桶.

如果我们写了 l而不是 [l] ，结果将是

*Main> bucketBy sum x[[0,3,2,1,1,2],[5,0],[1,9]]

but then we lose the structure of the innermost lists.

We’ve already constrained the type of bucketBy's result to be [[[α]]] and thus the type of the Map's elements. Say the next item l to fold is [1,2]. We want to append, (++), it to some other list of type [[Integer]], but the types don’t match.

*Main> [[0,3],[2,1]] ++ [1,2]<interactive>:1:21:    No instance for (Num [t0])      arising from the literal `2'    Possible fix: add an instance declaration for (Num [t0])    In the expression: 2    In the second argument of `(++)', namely `[1, 2]'    In the expression: [[0, 3], [2, 1]] ++ [1, 2]

Wrapping l gets us

*Main> [[0,3],[2,1]] ++ [[1,2]][[0,3],[2,1],[1,2]]

Generalizing further

You might stop with

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

甚至

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

并且非常高兴，因为它可以处理您的问题。

假设在路上你有一个不同的列表 y定义为

y :: [[Int]]
y = [[1,2],[2,1],[5,0],[0,3],[1,9]]

即使定义与 x 几乎相同, bucketBy对 y 没有用.

*Main> bucketBy sum y<interactive>:1:15:    Couldn't match expected type `Integer' with actual type `Int'    Expected type: [[Integer]]      Actual type: [[Int]]    In the second argument of `bucketBy', namely `y'    In the expression: bucketBy sum y

Let’s assume you can’t change the type of y for some reason. You might copy-and-paste to create another function, say bucketByInt, where the only change is replacing Integer with Int in the type annotations.

This would be highly, highly unsatisfying.

Maybe later you have some list of strings that you want to bucket according to the length of the longest string in each. In this imaginary paradise you could

*Main> bucketBy (maximum . map length) [["a","bc"],["d"],["ef","g"],["hijk"]][[["d"]],[["ef","g"],["a","bc"]],[["hijk"]]]

What you want is entirely reasonable: bucket some list of things using the given criterion. But alas

*Main> bucketBy (maximum . map length) [["a","bc"],["d"],["ef","g"],["hijk"]]<interactive>:1:26:    Couldn't match expected type `Integer' with actual type `[a0]'    Expected type: Integer -> Integer      Actual type: [a0] -> Int    In the first argument of `map', namely `length'    In the second argument of `(.)', namely `map length'

Again, you may be tempted to write bucketByString, but by this point, you’re ready to move away and become a shoe cobbler.

The typechecker is your friend. Go back to your definition of bucketBy that’s specific to Integer lists, simply comment out the type annotation and ask its type.

*Main> :t bucketBybucketBy :: Ord k => (b -> k) -> [b] -> [[b]]

Now you can apply bucketBy for the different cases above and get the expected results. You were already in paradise but didn’t know it!

Now, in keeping with good style, you provide annotations for the toplevel definition of bucketBy to help the poor reader, perhaps yourself. Note that you must provide the Ord constraint due to the use of insertWith', whose type is

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

您可能希望非常明确并为内部 go 提供注释。 ，但这需要使用 scoped type variables extension .

{-# LANGUAGE ScopedTypeVariables #-}

import Data.List (foldl')
import Data.Map (Map,elems,empty,insertWith')

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go :: Map b [a] -> a -> Map b [a]
        go m l = insertWith' (++) (eq l) [l] m

没有扩展名并带有类型注释

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]

类型检查器将因表单错误而失败

    Could not deduce (b ~ b1)    from the context (Ord b)      bound by the type signature for                 bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]      at prog.hs:(10,1)-(12,46)      `b' is a rigid type variable bound by          the type signature for            bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]          at prog.hs:10:1      `b1' is a rigid type variable bound by           the type signature for go :: Map b1 [a1] -> a1 -> Map b1 [a1]           at prog.hs:12:9    In the return type of a call of `eq'    In the second argument of `insertWith'', namely `(eq l)'    In the expression: insertWith' (++) (eq l) [l] m

This is because the typechecker treats the b on the inner type annotation as a distinct and entirely unrelated type b1 even though a human reader plainly sees the intent that they be the same type.

Read the scoped type variables documentation for details.

One last small surprise

You may wonder where the outer layer of brackets went. Notice that the type annotation generalized from

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]

到

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]

请注意 [Integer]本身是另一种类型，这里表示为 a .