Lists |
|
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! Accumulating speedThe 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. Duplicates removedFunction 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 L.A. 8/2002 |
|
|