1

Einfuhrung in dieFunktionale Programmierung

Aufgabenblatt 4

Wintersemester 2009/10

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

Aufgabe 1

b = [bin x [] | x <- [1..]]

where bin 0 res = res

bin x res = bin (x ‘div‘ 2) ((intToDigit $ x ‘mod‘ 2):res)

h = [hex x [] | x <- [1..]]

where hex 0 res = res

hex x res = hex (x ‘div‘ 16) ((intToHex $ x ‘mod‘ 16):res)

intToHex x

| x < 10 = intToDigit x

| otherwise = case x of

10 -> ’A’

11 -> ’B’

12 -> ’C’

13 -> ’D’

14 -> ’E’

15 -> ’F’

b’ = let start = ["1"]

in start ++ concat [[x ++ "0", x ++ "1"] | x <- b’]

Professur KIST, WS 09/10: EFP, Blatt 4 2

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

Aufgabe 1

genStream alpha =

let start = drop 1 alpha

in start ++ concat [map (x ++) alpha | x <- genStream alpha]

okt = genStream ["0","1","2","3","4","5","6","7"]

Professur KIST, WS 09/10: EFP, Blatt 4 3

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

Aufgabe 2

> map_Knoten :: (a -> c) -> Baum a b -> Baum c b

> map_Knoten f (Knoten a (l,lt) (r,rt)) =

> Knoten (f a) (l,map_Knoten f lt) (r,map_Knoten f rt)

> map_Knoten f (Blatt a) =

> Blatt (f a)

> map_Kanten :: (b -> c) -> Baum a b -> Baum a c

> map_Kanten f (Knoten a (l,lt) (r,rt)) =

> Knoten a (f l,map_Kanten f lt) (f r,map_Kanten f rt)

> map_Kanten f (Blatt a) =

> Blatt a

> map_KnotenKanten :: (a -> c) -> (b -> d) -> Baum a b -> Baum c d

> map_KnotenKanten f g (Knoten a (l,lt) (r,rt)) =

> Knoten (f a) (g l,map_KnotenKanten f g lt) (g r,map_KnotenKanten f g rt)

> map_KnotenKanten f g (Blatt a) =

> Blatt (f a)

Professur KIST, WS 09/10: EFP, Blatt 4 4

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

Aufgabe 2

allPaths (Blatt x) = [[x]]

allPaths (Knoten a (l,tl) (r,tr)) =

let pathl = allPaths tl

pathr = allPaths tr

in map (a:) (pathl ++ pathr)

Professur KIST, WS 09/10: EFP, Blatt 4 5

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

Aufgabe 2

allPathsWL (Blatt x) = [([x],0)]

allPathsWL (Knoten a (l,tl) (r,tr)) =

let pathl = allPathsWL tl

pathr = allPathsWL tr

fl = \(p,len) -> (a:p,l+len)

fr = \(p,len) -> (a:p,r+len)

in (map fl pathl) ++ (map fr pathr)

Professur KIST, WS 09/10: EFP, Blatt 4 6

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | u <- [3..30], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | w <- [1..10], even u]

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | w <- [1..10], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> [[1..u]|even u]) [1..10])

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> [[1..u]|even u]) [1..10])

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> [[1..u]|even u]) [1..10])

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> if even u then [[1..u]|] else []) [1..10])

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> [[1..u]|even u]) [1..10])

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> if even u then [[1..u]|] else []) [1..10])

Professur KIST, WS 09/10: EFP, Blatt 4 7

Blatt 4Aufgabe 1Aufgabe 2Aufgabe 3

List Comprehensions weg kodieren

ZFgen [e|x <- xs,Q] = concatMap (\ x -> [e|Q]) xs

ZFguard [e|p, Q] = if p then [e|Q] else []

ZFnil [e|] = [e]

[x*3 | z <- [ [1..u] | u <- [3..30], even u], x <- z, odd x]

= concatMap (\z -> [x*3|x <- z, odd x]) [ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> [x*3|odd x]) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3|] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

[ [1..u] | u <- [3..30], even u]

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> [[1..u]|even u]) [1..10])

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> if even u then [[1..u]|] else []) [1..10])

= concatMap (\z -> (concatMap (\x -> if odd x then [x*3] else []) z))

(concatMap (\w -> if even u then [[1..u]] else []) [1..10])

Professur KIST, WS 09/10: EFP, Blatt 4 7