您没有说明是否要自己编写代码,还是可以从一些标准函数中组合。
import Data.List
g s = map (\x -> ([head x], length x)) . group . sort $ s
这是编写代码的标准快速而简单的方法。
好的,你最初的想法是无指针编程(某个旋律在我脑海中响起...):
frequencyOfElt :: (Eq a) => [a] -> [(a,Int)]
frequencyOfElt xs = countElt (unique xs) xs
where
unique [] = []
unique (x:xs) = x : unique (filter (/= x) xs)
countElt ref target =
zip
ref $
map length $
zipWith ($)
(zipWith ($) (repeat (filter . (==))) ref)
(repeat target)
我已经将类型更改为更合理的[a] -> [(a,Int)]
。注意,
zipWith ($) fs (repeat z) === map ($ z) fs
zipWith ($) (repeat f) zs === map (f $) zs === map f zs
因此,代码简化为:
countElt ref target =
zip
ref $
map length $
map ($ target)
(zipWith ($) (repeat (filter . (==))) ref)
然后
countElt ref target =
zip
ref $
map length $
map ($ target) $
map (filter . (==)) ref
但是map f $ map g xs === map (f.g) xs
,因此
countElt ref target =
zip
ref $
map (length . ($ target) . filter . (==)) ref
用列表推导式写会更加清晰(依我个人的口味)。
countElt ref target =
[ (c, (length . ($ target) . filter . (==)) c) | c <- ref]
== [ (c, length ( ($ target) ( filter (== c)))) | c <- ref]
== [ (c, length $ filter (== c) target) | c <- ref]
这给我们提供了一个重新编写 (1) 的想法,进一步改写如下:
countElt ref target =
zip <*> map (length . (`filter` target) . (==)) $ ref
但是这种对无点代码的痴迷在这里变得毫无意义。
回到易读的列表推导式,使用一个标准的 nub
函数,它相当于你的 unique
,你的想法变成了这样
import Data.List
frequencyOfElt xs = [ (c, length $ filter (== c) xs) | c <- nub xs]
这个算法实际上是二次的(
~ n^2
),所以比上面的第一个版本更差,因为它被
sort
支配,即线性对数级别(
~ n log(n)
)。
这段代码可以通过等效转换进一步操作:
= [ (c, length . filter (== c) $ sort xs) | c <- nub xs]
...因为在列表中搜索与在已排序的列表中搜索相同。在这里做更多的工作——它会有回报吗?...
= [ (c, length . filter (== c) $ sort xs) | (c:_) <- group $ sort xs]
...对吗?但是现在,group
已经通过(==)
将它们分组,因此filter
调用不需要重复group
已经完成的工作:
= [ (c, length . get c . group $ sort xs) | (c:_) <- group $ sort xs]
where get c gs = fromJust . find ((== c).head) $ gs
= [ (c, length g) | g@(c:_) <- group $ sort xs]
= [ (head g, length g) | g <- group (sort xs)]
= (map (head &&& length) . group . sort) xs
不是吗?这里就是从本文开头推导出来的同样的线性对数时间复杂度算法,实际上是通过分解出隐藏的公共计算来从您的代码中“派生”出来的,使它们可供重用和简化代码。
where
子句中的绑定必须从同一列开始。 - Daniel Fischerans
和unique
这两个在同一个 where 子句中的列。 - Ingomap[(=='a'),(==',b'),(==',c')]
的含义是什么吗? - Ingo