Haskell 如何使用折叠函数重写代码？

Question

我想使用折叠函数重写（或升级！:)）我的两个函数 hist 和 sort。但是由于我才刚刚开始 Haskell-way，所以我不知道该怎么做。

首先我定义了Insertion,Table并导入了Data.Char:

type Insertion = (Char, Int)
type Table = [Insertion]
import Data.Char

然后我为hist实现了以下代码：

hist :: String -> Table
hist[] = []
hist(x:xs) = sortBy x (hist xs) where
    sortBy x [] = [(x,1)]
    sortBy x ((y,z):yzs)
      | x == y = (y,z+1) : yzs 
      | otherwise = (y,z) : sortBy x yzs

而这个 sort:

sort :: Ord a => [a] -> [a]
sort [] = []
sort (x:xs) = paste x (sort xs)

paste :: Ord a => a -> [a] -> [a]
paste y [] = [y]
paste y (x:xs)
    | x < y = x : paste y xs 
    | otherwise = y : x : xs

接下来我能做什么？如何使用折叠函数来实现它们？

Answer 1

列表上的

foldr f z 将列表 (:) 的“cons”替换为 f 并将空列表 [] 替换为 z.

这意味着对于像 [1,4,2,5] 这样的列表，我们因此获得 f 1 (f 4 (f 2 (f 5 z)))，因为 [1,4,2,5] 是 1 : 4 : 2 : 5 : [] 或更规范的 (:) 1 ((:) 4 ((:) 2 ((:) 5 []))) 的缩写.

例如sort函数可以用fold函数代替：

sort :: Ord a => [a] -> [a]
sort = foldr paste []

因为 sort [1,4,2,5] 等同于 paste 1 (paste 4 (paste 2 (paste 5 [])))。因此，f 将一个元素作为第一个参数，并将对列表其余部分 foldr f z 调用的结果作为第二个参数，

我留下 hist 作为练习。

Haskell 如何使用折叠函数重写代码？

Haskell How to rewrite a code using fold-function?

list

sorting

haskell

histogram

fold