仅使用比较运算符计算列表中每个元素的频率

Question

我是Haskell的新手，我必须计算列表中元素的频率，并在键值对列表中返回它，其中key是列表中的元素，值是它在列表中出现的次数。例如：

对于输入[0,2,2,0,2,5,0,2]输出应[(0,3),(2,4),(5,1)]

这里的问题是我们必须在不使用除比较之外的任何预定义函数的情况下执行此操作。

import Data.Map (fromListWith, toList)
frequency :: (Ord a) => [a] -> [(a, Int)]
frequency xs = toList (fromListWith (+) [(x, 1) | x <- xs])

这有效，但 toList 和 fromListWith 归类为预定义函数。有没有办法在不使用任何数据.地图函数的情况下做到这一点？

Answer 1

试试这个

freq:: (Ord a) => [a] -> [(a, Int)]
freq []      = []
freq (x: xs) = ins x (freq xs)
   where 
      ins :: (Ord a) => a -> [(a, Int)] -> [(a, Int)]
      ins x ((fk, fv): fs) | x == fk = (fk, fv + 1): fs 
      ins x ((fk, fv): fs) | x <  fk = (x, 1): (fk, fv): fs       
      ins x ((fk, fv): fs)           = (fk, fv): ins x fs             
      ins x []                       = (x, 1): []             

ins函数在地图中插入单个元素。它递归地穿过地图。

如果当前元素等于键，则递增该值。

ins x ((fk, fv): fs) | x == fk = (fk, fv + 1): fs 

如果当前元素小于键，则在映射中插入新条目。

ins x ((fk, fv): fs) | x <  fk = (x, 1): (fk, fv): fs

否则(如果元素更大(，它会尝试在映射的尾部插入元素。

ins x ((fk, fv): fs)           = (fk, fv): ins x fs

最后一部分只是当地图为空时处理情况。