Kapitel 6: Programmiertechniken

hugs HigherOrder
ghc -c HigherOrder.lhs

> module HigherOrder
> where
> import Char
> import List (partition)

> r                             =  5 :: Double
> volume_of_r                   =  3/4 * pi * r^3

> volume r                      =  3/4 * pi * r^3
> volume_of_r'                  =  volume r

Funktionen als Argumente.

> qsortBy                       :: (a -> a -> Bool) -> [a] -> [a]
> qsortBy (<=) []               =  []
> qsortBy (<=) (a : x)          =  qsortBy (<=) l ++ a : qsortBy (<=) r
>     where (l, r)              =  partition (<= a) x
>
> qsort                         :: (Ord a) => [a] -> [a]
> qsort                         =  qsortBy (<=)

map-Funktionen.

> inclist1 []                   =  []
> inclist1 (a : x)              =  a + 1     : inclist1 x
>
> strupr1 []                    =  []
> strupr1 (a : x)               =  toUpper a : strupr1  x

> map1                          :: (a -> b) -> [a] -> [b]
> map1 f []                     =  []
> map1 f (a : x)                =  f a : map1 f x

> inclist2                      =  map (+ 1)
> strupr2                       =  map toUpper

> map2 f x                      =  [ f a | a <- x ]

> mapMaybe                      :: (a -> b) -> Maybe a -> Maybe b
> mapMaybe f Nothing            =  Nothing
> mapMaybe f (Just a)           =  Just (f a)

> data Tree lab                 =  Node lab [Tree lab]
>
> mapTree                       :: (a -> b) -> Tree a -> Tree b
> mapTree f (Node a ts)         =  Node (f a) (map (mapTree f) ts)

< class Functor f where
<     fmap                      :: (a -> b) -> f a -> f b

< instance Functor Maybe where
<     fmap f Nothing            =  Nothing
<     fmap f (Just a)           =  Just (f a)

> instance Functor Tree where
>     fmap f (Node a ts)        =  Node (f a) (fmap (fmap f) ts)

fold-Funktionen.

> sum1 []                       =  0
> sum1 (a : x)                  =  a + sum1 x
>
> sequence1_ []                 =  return ()
> sequence1_ (a : as)           =  a >> sequence1_ as

< foldr                         :: (a -> b -> b) -> b -> [a] -> b
< foldr (*) e []                =  e
< foldr (*) e (a:x)             =  a * foldr (*) e x

> sum2                          =  foldr (+) 0
> sequence2_ as                 =  foldr (>>) (return ()) as

> fold                          :: (a -> [b] -> b) -> Tree a -> b
> fold f (Node a ts)            =  f a (map (fold f) ts)

> sumup                         =  fold (\a ns -> a + sum ns)
> size                          =  fold (\_ ns -> 1 + sum ns)
> height                        =  fold (\_ ns -> 1 + maximum ns)
> preorder                      =  fold (\a xs -> a : concat xs)