Kapitel 2: Ausdrücke und Definitionen

hugs Expressions
ghc -c BinTree.lhs Expressions.lhs

> module Expressions
> where
> import Prelude hiding ( concat, head, take )
> import BinTree hiding ( splitAt, build )
> import List ( partition )

> fac                           :: (Integral a) => a -> a
> fac n | n == 0                =  1
>       | otherwise             =  n * fac (n - 1)

fac 10 :: Int
fac 10 :: Integer
fac 100 :: Int
fac 100 :: Integer

Listenbeschreibungen.

> elem1 a x                     =  or [ a==b | b <- x ]
> concat xs                     =  [ a | x <- xs, a <- x ]

Naive Definition von Quicksort.

> qsort1 []                     =  []
> qsort1 (a : x)                =  qsort1 [ b | b <- x, b <= a ]
>                               ++ [a]
>                               ++ qsort1 [ b | b <- x, b > a ]

qsort1 [17, 3, 9, 21, 2, 33]
qsort1 [1000, 999 .. 1]

> perms                         :: [a] -> [[a]]
> perms []                      =  [[]]
> perms x                       =  [ a : y' | (a, y) <- remove x, y' <- perms y ]
>
> remove                        :: [a] -> [(a,[a])]
> remove []                     =  []
> remove (a : x)                =  (a, x) : [ (b, a : y) | (b, y) <- remove x ]

perms [1 .. 6]

> type Board			=  [Int]
>
> queens			:: Int -> [Board]
> queens n                      =  place n [] [] [1 .. n]
>
> place c d1 d2 rs
>   | c == 0                    =  [[]]
>   | otherwise                 =  [ q : qs
>                                  | (q, rs') <- remove rs,
>                                    (q - c) `notElem` d1,
>                                    (q + c) `notElem` d2,
>                                    qs <- place (c - 1) ((q - c) : d1) ((q + c) : d2) rs' ]

queens 8
queens 12 !! 0

Funktionen.

> addInt                        :: Int -> Int -> Int
> addInt a b                    =  a + b

> addInt'                       :: (Int, Int) -> Int
> addInt' (a, b)                =  a + b

|case|-Ausdrücke.

> elem2 a []                    =  False
> elem2 a (b : x)               =  a == b || elem2 a x

> elem3				:: (Eq a) => a -> [a] -> Bool
> elem3                         =  \a y -> case y of
>                                      []    -> False
>                                      b : x -> a == b || elem3 a x

Beachte: die Typsignatur ist notwendig!

> qsort2                        :: (Ord a) => [a] -> [a]
> qsort2 []                     =  []
> qsort2 [a]                    =  [a]
> qsort2 (a : x)                =  partition [] [] x
>     where
>     partition l r []          =  qsort2 l ++ a : qsort2 r
>     partition l r (b : y)
>         | b <= a              =  partition (b : l) r y
>         | otherwise           =  partition l (b : r) y

qsort2 [17, 3, 9, 21, 2, 33]
qsort3 [1000, 999 .. 1]

> head (a : x)                  =  a

> take (n + 1) (a : x)          =  a : take n x
> take _     _                  =  []

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

qsort3 [17, 3, 9, 21, 2, 33]
qsort3 [1000, 999 .. 1]

> build                         :: [a] -> Tree a
> build x                       =  fst (buildn (length x) x)
>
> buildn                        :: Int -> [a] -> (Tree a, [a])
> buildn 0 x                    =  (Empty, x)
> buildn (n + 1) x              =  (Node l a r, z)
>     where m                   =  n `div` 2
>           (l, a : y)          =  buildn m x
>           (r, z)              =  buildn (n - m) y

build [1 .. 100]