The length of the empty list, , also known as nil,
is zero, and
the length of a non-empty list, (_:xs),
is 1 plus the length of xs.
The result of appending the empty list, ,
and a list, xs, is just xs.
The result of appending a non-empty list, (h:t),
and xs is a list whose head is h
and whose tail is
module List (module List, module Unique, module Reverse)-- export all where import Unique import Reverse len  = 0 len (_:xs) = 1 + len xs append  xs = xs -- same as (++) in H98 append (h:t) xs = h:(append t xs)
A small theorem
Try that on C++ code!
The fast, i.e. O(|L|)-time, way to reverse a list L uses an auxiliary function, r, which has two parameters, an input parameter and an accumulating parameter, ans. The accumulating parameter grows as the input list shrinks:
module Reverse (module Reverse) where rev xs = -- O(|xs|)-time let r  ans = ans -- done r (h:t) ans = r t (h:ans) -- accumulate in r xs 
We can prove that the fast reverse function above is equivalent to the obvious but slow version:
Note that slowR xs takes O(|xs|2)-time because of those calls on append.
Function unique removes duplicate values from a list. The result is a list, r, which is built by a function u. This function depends on r, so u and r are mutually recursive, making this an example of a circular program [more].
module Unique ( module Unique ) where unique xs = -- remove duplicates let r = u xs 0 -- result list u  _ =  -- build result u (x:xs) n = if member x r n then u xs n else x:(u xs (n+1)) member e xs 0 = False member y (x:xs) n = x==y || member y xs (n-1) in r
Note that unique operates correctly, i.e. lazily, on infinite lists.
The simple driver `Main.hs' exercises the above operations on lists.
module Main where import List main = print ( append [1,2,3] [4,5,6] ) >> print ( rev [1,2,3,4] ) >> print ( unique [1,2,1,3,2,4] )
Note that Haskell 98 provides a large number of useful operations on lists
in Prelude PreludeList