Haskell How to rewrite a code using fold-function?

Question

I want to rewrite (or upgrade! :) ) my two functions, hist and sort, using fold-functions. But since I am only in the beginning of my Haskell-way, I can't figure out how to do it.

First of all, I have defined Insertion, Table and imported Data.Char:

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

Then I have implemented the following code for 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

And this one for 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

What can I do next? How can I use the fold-functions to implement them?

Answer 1

foldr f z on a list replaces the "cons" of the list (:) with f and the empty list [] with z.

This thus means that for a list like [1,4,2,5], we thus obtain f 1 (f 4 (f 2 (f 5 z))), since [1,4,2,5] is short for 1 : 4 : 2 : 5 : [] or more canonical (:) 1 ((:) 4 ((:) 2 ((:) 5 []))).

The sort function for example can be replaced with a fold function:

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

since sort [1,4,2,5] is equivalent to paste 1 (paste 4 (paste 2 (paste 5 []))). Here f thus takes as first parameter an element, and as second parameter the result of calling foldr f z on the rest of the list,

I leave hist as an exercise.