List reversing

   rev :: [t] -> [t]
   rev [] = []
   rev (a:x) = rev x ++ [a]

Source code: reverse.hs.

The program was loaded into Hugs and run with lists of length between 10 and 3000. The number of reductions required for computing the length of the lists was compared with the number of reductions for computing the length of the reversed lists. The number of reductions for computing the length of a list is seen to be linear wheras the number of reductions for computing the length of the reversed list is quadratic. The reason that rev requires a quadratic number of reductions is because list catenation requires a number of reductions that is proportional to the length of the first list.

Note: The function reverse contained in the prelude of Hugs only requires a linear number of reductions. Another implementation only requiring a linear number of reductions is reverse2.hs.

Results of experiments