计算有序列表上的元素

Question

我想做一个Haskell函数,其中输入(字符串列表)是有序的(总是.输入只有在有序时才有效),我想得到每个不同字符串的出现次数.

例:

ContaOcs["a", "a", "b", "c", "c", "c", "d"]

应该返回:

[(2,"a"), (1,"b"), (3,"c"), (1,"d")]

这是我正在尝试做的事情:

module Main where

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = [_,_]
contaOcs [x] = [1,x]
contaOcs (i, x1:x2:xs)
 | x1 == x2 =  (i+1,(x2:xs))
 | otherwise = (0, (x2:xs))

但是这段代码有一些错误,我不太清楚我应该怎样做才能实现这一点我是功能编程和Haskell的新手.任何人都可以帮我一些信息吗？

谢谢你的帮助.

Answer 1

有一些语法问题以及类型的问题.第一行看起来像:

contaOcs [] = [_,_]

但是_结果中的下划线()没有任何意义,你只能在其中构造带有值的列表.当我们计算空列表的出现次数时,结果将是一个空列表,所以contaOcs [] = [].

至于第二个:

   contaOcs [x] = [1,x]

在这里,您的目标是返回一个包含两个元素的列表:a 1和an x(是a String).在Haskell中,列表的元素都具有相同的类型.你可以做的是返回一个2元组的列表,第一个项目是an Int,第二个是a String,就像签名所示,但是你需要将值包装成2元组,比如contaOcs [x] = [(1,x)].

在你的最后一句中,你写道:

contaOcs (i, x1:x2:xs) = ...

没有多大意义:输入类型是一个列表(这里是Strings),而不是带有a的2元组Int和字符串列表.

所以输入看起来像:

contaOcs (x1:x2:xs) = ...

输出,(i+1,(x2:xs))也不与签名中提出的输出类型"和谐",这看起来像一个带有a的2元组Int和Strings 的列表,所以(Int, [String])不是[(Int, String)].

基于以上评论,我们得出了类似的结果:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:x2:xs)
     | x1 == x2 =  -- ...
     | otherwise = -- ...

所以现在有两个部分,填补万一x1并且x2是不相等的,这意味着我们可以先产生一个元组(1, x1)列表,之后的结果contaOcs就行了(其余x2在内),所以:

(1, x1) : contaOcs (x2:xs)

在后一种情况下,这意味着我们首先对contaOcswith 进行递归调用(x2:xs),然后递增该列表第一项的计数器.我们确信这样的元素存在,因为我们使用包含至少一个元素的列表进行递归调用,并且通过归纳,这意味着结果至少包含一个元素,因为基本情况包含一个元素,并且递归情况要么将元素添加到结果中,要么更新这些元素.

所以我们可以使用模式保护,并操纵结果,如:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:x2:xs)
     | x1 == x2, ((yi, yv):ys) <- contaOcs (x2:xs) = (yi+1, yv) : ys
     | otherwise = (1, x1) : contaOcs (x2:xs)

我们也可以使用" as-pattern ":我们只需要引用列表的尾部x2,而不是xs:

contaOcs :: [String] -> [(Int, String)]
contaOcs [] = []
contaOcs [x] = [(1,x)]
contaOcs (x1:xs@(x2:_))
     | x1 == x2, ((yi, yv):ys) <- contaOcs xs = (yi+1, yv) : ys
     | otherwise = (1, x1) : contaOcs xs

然而,上述不是很优雅.在这里使用累加器可能更好,我将其作为练习.