我正在尝试学习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,但我似乎无法使其工作.
该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]]]
elemsData.Map的应用程序提供了发生了什么的线索.
elems :: Map ? ? -> [?]O(n).按照键的升序返回地图的所有元素.
Run Code Online (Sandbox Code Playgroud)elems (fromList [(5,"a"), (3,"b")]) == ["b","a"] elems empty == []
Map将某种类型κ的值与另一种可能不同的类型α的值相关联.在您的问题的示例中,您从x哪个类型开始
*Main> :type x x :: [[Integer]]
也就是说,x是整数列表的列表.您想要的结果分区的类型x是
*Main> :t [[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]] [[[0,3],[2,1],[1,2]],[[5,0]],[[1,9]]] :: Num ? => [[[?]]]
或列表列表,其中后面的每个列表本身都是具有相同总和的列表.该Num ? =>位是将类型τ约束为类型类的实例的上下文Num.为我们感到高兴,Integer是这样一种类型:
*Main> :info Integer data Integer … instance Num Integer -- Defined in GHC.Num …
我们知道分区的类型是[[[Integer]]].这个类型类的废话似乎不必要地挑剔,但我们将在短时间内再次需要这个概念.(为了让您了解正在发生的事情,类型检查器没有足够的信息来判断文字是否0属于类型Int或Integer.)
每个子列表包含具有相同总和的列表.换句话说,存在从总和到整数列表列表的映射.因此,使用的Map的类型bucketBy必须类似
Map Integer [[Integer]]
例如,使用总和3,我们将列表关联起来
[ [0,3]
, [2,1]
, [1,2]
]
折叠是一种非常普遍的模式.左侧折叠foldl和Haskell中的朋友允许您在列表左侧的零值开头的列表元素之间"插入"运算符.例如,[5,3,9,1]表示为左折叠的总和是
((((0 + 5) + 3) + 9) + 1)
要么
foldl (+) 0 [5,3,9,1]
也就是说,从基值0开始,我们连续添加列表的元素并累加总和.
回想一下bucketBycontains 的定义
elems . foldl' go empty
这意味着左侧折叠的结果必须是类型Map Integer [[Integer]],我们折叠的零值是该类型的空白地图,并go以某种方式将列表的每个连续值添加到地图中.
请注意,这foldl'是严格的表亲foldl,但严格超出了这个答案的范围.(另请参阅HaskellWiki上的"堆栈溢出".)
考虑到的类型 foldl'
*Main> :t foldl' foldl' :: (a -> b -> a) -> a -> [b] -> a
我们应该在应用程序中有三个参数,但上面的代码中只有两个参数.这是因为代码是以无点样式编写的.由于部分应用,您的列表是隐含的foldl'.
回想一下上面的总和 - 例子.没有最终参数的应用程序的类型是
*Main> :t foldl (+) 0 foldl (+) 0 :: Num b => [b] -> b
部分应用程序允许我们创建新功能.在这里,我们定义了一个函数,用于计算某些数字列表中的数字.嗯,听起来很熟悉.
*Main> :t sum sum :: Num a => [a] -> a
所述.组合子表达功能的组合物.它的名称被选择为类似于数学教科书中常见的符号g∘f,意思是"先做f然后从结果中计算g."这正是定义中发生的事情bucketBy:将值列表折叠成Map然后获取Map的值.
在你的评论中,你问的目的是什么m.使用显式类型注释,我们可以定义go为
...
where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
go m l = insertWith' (++) (eq l) [l] m
匹配变量与类型,m是我们到目前为止累积的地图,并且l是Integer我们想要投入适当存储桶的下一个列表.回想一下,这eq是外部的争论bucketBy.
我们可以使用控制新项目进入地图的方式insertWith'.(按照惯例,名称以尾随引号结尾的函数是严格的变体.)
该(++)组合子追加列表.应用程序eq l确定适当的存储桶l.
如果我们写的l而不是[l],结果就是想成为
*Main> bucketBy sum x [[0,3,2,1,1,2],[5,0],[1,9]]
但后来我们失去了最里面的名单的结构.
我们已经限制了bucketBy结果[[[?]]]的类型,从而限制了Map元素的类型.说下一个l要折叠的项目是[1,2].我们想要将(++)它附加到其他类型的列表中[[Integer]],但类型不匹配.
*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]
环绕l得到了我们
*Main> [[0,3],[2,1]] ++ [[1,2]] [[0,3],[2,1],[1,2]]
你可能会停下来
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
我们假设你不能y因某种原因改变类型.你可能会复制和粘贴创建另一个函数,说bucketByInt,这里唯一的变化是更换Integer用Int的类型注释.
这将是高度,非常不满意的.
也许以后你会根据每个字符串中最长字符串的长度来填充一些字符串列表.在这个想象中的天堂,你可以
*Main> bucketBy (maximum . map length) [["a","bc"],["d"],["ef","g"],["hijk"]] [[["d"]],[["ef","g"],["a","bc"]],[["hijk"]]]
你想要的是完全合理的:使用给定的标准来填充一些事物列表.可惜
*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'
再一次,你可能会想写bucketByString,但到了这一步,你已经准备好离开并成为一个鞋匠.
typechecker是你的朋友.回到您bucketBy对Integer列表特定的定义,只需注释掉类型注释并询问其类型.
*Main> :t bucketBy bucketBy :: Ord k => (b -> k) -> [b] -> [[b]]
现在您可以申请bucketBy上述不同的案例并获得预期的结果.你已经在天堂,但不知道它!
现在,为了保持良好的风格,您需要为顶级定义提供注释,bucketBy以帮助可怜的读者,也许是您自己.请注意,Ord由于使用了insertWith'类型,您必须提供约束
insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
您可能希望非常明确并为内部提供注释go,但这需要使用范围类型变量扩展.
{-# 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
这是因为b类型检查器将内部类型注释视为一种独特且完全不相关的类型,b1即使人类读者明白地看到它们是相同类型的意图.
有关详细信息,请阅读作用域类型变量文档.
您可能想知道括号外层的位置.请注意,类型注释是从
bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
至
bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]
请注意,这[Integer]本身就是另一种类型,在此表示为a.