Haskell Beginner Exercises with Tests
Follow-on from Haskell Exercises for Beginners
-- TOTAL marks: /66 module Exercises where import Prelude hiding (sum, length, map, filter, maximum, reverse, succ, pred) -- BEGIN Helper functions and data types -- The custom list type data List t = Nil | Cons t (List t) deriving Eq instance (Show t) => Show (List t) where show = show . toList where toList Nil = [] toList (Cons h t) = h : toList t -- the custom numeric type data Natural = Zero | Succ Natural deriving Eq one = Succ Zero two = Succ one three = Succ two instance Show Natural where show = show . toInt where toInt Zero = 0 toInt (Succ x) = 1 + toInt x -- functions over Natural that you may consider using succ :: Natural -> Natural succ = Succ pred :: Natural -> Natural pred Zero = error "bzzt. Zero has no predecessor in naturals" pred (Succ x) = x -- functions over List that you may consider using foldRight :: (a -> b -> b) -> b -> List a -> b foldRight _ b Nil = b foldRight f b (Cons h t) = f h (foldRight f b t) foldLeft :: (b -> a -> b) -> b -> List a -> b foldLeft _ b Nil = b foldLeft f b (Cons h t) = let b' = f b h in b' `seq` foldLeft f b' t reduceRight :: (a -> a -> a) -> List a -> a reduceRight _ Nil = error "bzzt. reduceRight on empty list" reduceRight f (Cons h t) = foldRight f h t reduceLeft :: (a -> a -> a) -> List a -> a reduceLeft _ Nil = error "bzzt. reduceLeft on empty list" reduceLeft f (Cons h t) = foldLeft f h t -- END Helper functions and data types -- BEGIN Exercises -- Exercise 1 -- Relative Difficulty: 1 -- Correctness: 2.0 marks -- Performance: 0.5 mark -- Elegance: 0.5 marks -- Total: 3 add :: Natural -> Natural -> Natural add = error "todo" -- Exercise 2 -- Relative Difficulty: 2 -- Correctness: 2.5 marks -- Performance: 1 mark -- Elegance: 0.5 marks -- Total: 4 sum :: List Int -> Int sum = error "todo" -- Exercise 3 -- Relative Difficulty: 2 -- Correctness: 2.5 marks -- Performance: 1 mark -- Elegance: 0.5 marks -- Total: 4 length :: List a -> Int length = error "todo" -- Exercise 4 -- Relative Difficulty: 5 -- Correctness: 4.5 marks -- Performance: 1.0 mark -- Elegance: 1.5 marks -- Total: 7 map :: (a -> b) -> List a -> List b map = error "todo" -- Exercise 5 -- Relative Difficulty: 5 -- Correctness: 4.5 marks -- Performance: 1.5 marks -- Elegance: 1 mark -- Total: 7 filter :: (a -> Bool) -> List a -> List a filter = error "todo" -- Exercise 6 -- Relative Difficulty: 5 -- Correctness: 4.5 marks -- Performance: 1.5 marks -- Elegance: 1 mark -- Total: 7 append :: List a -> List a -> List a append = error "todo" -- Exercise 7 -- Relative Difficulty: 5 -- Correctness: 4.5 marks -- Performance: 1.5 marks -- Elegance: 1 mark -- Total: 7 flatten :: List (List a) -> List a flatten = error "todo" -- Exercise 8 -- Relative Difficulty: 7 -- Correctness: 5.0 marks -- Performance: 1.5 marks -- Elegance: 1.5 mark -- Total: 8 flatMap :: List a -> (a -> List b) -> List b flatMap = error "todo" -- Exercise 9 -- Relative Difficulty: 8 -- Correctness: 3.5 marks -- Performance: 3.0 marks -- Elegance: 2.5 marks -- Total: 9 maximum :: List Int -> Int maximum = error "todo" -- Exercise 10 -- Relative Difficulty: 10 -- Correctness: 5.0 marks -- Performance: 2.5 marks -- Elegance: 2.5 marks -- Total: 10 reverse :: List a -> List a reverse = error "todo" -- END Exercises -- BEGIN Tests for Exercises main :: IO () main = let showNil = show (Nil :: List Int) results = [ -- add ("add", show (add one two) , show three), ("add", show (add Zero two) , show two), -- sum ("sum", show (sum (Cons 1 (Cons 2 (Cons 3 Nil)))) , show 6), ("sum", show (sum Nil) , show 0), -- length ("length", show (length (Cons 'a' (Cons 'b' (Cons 'c' Nil)))) , show 3), ("length", show (length Nil) , show 0), -- map ("map", show (map (+1) (Cons 1 (Cons 2 (Cons 3 Nil)))) , show (Cons 2 (Cons 3 (Cons 4 Nil)))), ("map", show (map (+1) Nil) , showNil), -- filter ("filter", show (filter even (Cons 1 (Cons 2 (Cons 3 Nil)))) , show (Cons 2 Nil)), ("filter", show (filter even Nil) , showNil), -- append ("append", show (append (Cons 1 (Cons 2 (Cons 3 Nil))) (Cons 4 Nil)) , show (Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil))))), ("append", show (append (Cons 1 (Cons 2 (Cons 3 Nil))) Nil) , show (Cons 1 (Cons 2 (Cons 3 Nil)))), -- flatten ("flatten", show (flatten (Cons (Cons 1 (Cons 2 Nil)) (Cons (Cons 3 (Cons 4 Nil)) Nil))) , show (Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil))))), -- flatMap ("flatMap", show (flatMap (Cons 1 (Cons 2 (Cons 3 Nil))) (\n -> Cons (n+1) (Cons (n+2) Nil))) , show (Cons 2 (Cons 3 (Cons 3 (Cons 4 (Cons 4 (Cons 5 Nil))))))), -- maximum ("maximum", show (maximum (Cons 3 (Cons 1 (Cons 2 Nil)))) , show 3), -- reverse ("reverse", show (reverse (Cons 1 (Cons 2 (Cons 3 Nil)))) , show (Cons 3 (Cons 2 (Cons 1 Nil)))) ] check (n, a, b) = do print ("=== " ++ n ++ " ===") print (if a == b then "PASS" else "FAIL Expected: " ++ b ++ " Actual: " ++ a) in mapM_ check results -- END Tests for Exercises
May 8th, 2010 at 11:46 pm
Thanks for putting this together. It was definitely very helpful, as I’m just starting to play around with Haskell.
Now it’s on to the cryptic intermediate exercises
LS0gVE9UQUwgbWFya3M6ICAgIC82Ng0KIA0KbW9kdWxlIEV4ZXJjaXNlcyB3aGVyZQ0KIA0KaW1wb3J0IFByZWx1ZGUgaGlkaW5nIChzdW0sIGxlbmd0aCwgbWFwLCBmaWx0ZXIsIG1heGltdW0sIHJldmVyc2UsIHN1Y2MsIHByZWQpDQogDQotLSBCRUdJTiBIZWxwZXIgZnVuY3Rpb25zIGFuZCBkYXRhIHR5cGVzDQogDQotLSBUaGUgY3VzdG9tIGxpc3QgdHlwZQ0KZGF0YSBMaXN0IHQgPSBOaWwgDQoJCQl8IENvbnMgdCAoTGlzdCB0KSBkZXJpdmluZyBFcQ0KIA0KaW5zdGFuY2UgKFNob3cgdCkgPT4gU2hvdyAoTGlzdCB0KSB3aGVyZQ0KICBzaG93ID0gc2hvdyAuIHRvTGlzdA0KICAgIHdoZXJlDQogICAgdG9MaXN0IE5pbCA9IFtdDQogICAgdG9MaXN0IChDb25zIGggdCkgPSBoIDogdG9MaXN0IHQNCiANCi0tIHRoZSBjdXN0b20gbnVtZXJpYyB0eXBlDQpkYXRhIE5hdHVyYWwgPSBaZXJvIA0KCQkJIHwgU3VjYyBOYXR1cmFsIGRlcml2aW5nIEVxDQpvbmUgPSBTdWNjIFplcm8NCnR3byA9IFN1Y2Mgb25lDQp0aHJlZSA9IFN1Y2MgdHdvDQogDQppbnN0YW5jZSBTaG93IE5hdHVyYWwgd2hlcmUNCiAgc2hvdyA9IHNob3cgLiB0b0ludA0KICAgIHdoZXJlDQogICAgdG9JbnQgWmVybyA9IDANCiAgICB0b0ludCAoU3VjYyB4KSA9IDEgKyB0b0ludCB4DQogDQotLSBmdW5jdGlvbnMgb3ZlciBOYXR1cmFsIHRoYXQgeW91IG1heSBjb25zaWRlciB1c2luZw0Kc3VjYyA6OiBOYXR1cmFsIC0+IE5hdHVyYWwNCnN1Y2MgPSBTdWNjDQogDQpwcmVkIDo6IE5hdHVyYWwgLT4gTmF0dXJhbA0KcHJlZCBaZXJvID0gZXJyb3IgImJ6enQuIFplcm8gaGFzIG5vIHByZWRlY2Vzc29yIGluIG5hdHVyYWxzIg0KcHJlZCAoU3VjYyB4KSA9IHgNCiANCi0tIGZ1bmN0aW9ucyBvdmVyIExpc3QgdGhhdCB5b3UgbWF5IGNvbnNpZGVyIHVzaW5nDQpmb2xkUmlnaHQgOjogKGEgLT4gYiAtPiBiKSAtPiBiIC0+IExpc3QgYSAtPiBiDQpmb2xkUmlnaHQgXyBiIE5pbCA9IGINCmZvbGRSaWdodCBmIGIgKENvbnMgaCB0KSA9IGYgaCAoZm9sZFJpZ2h0IGYgYiB0KQ0KIA0KZm9sZExlZnQgOjogKGIgLT4gYSAtPiBiKSAtPiBiIC0+IExpc3QgYSAtPiBiDQpmb2xkTGVmdCBfIGIgTmlsID0gYg0KZm9sZExlZnQgZiBiIChDb25zIGggdCkgPSBsZXQgYicgPSBmIGIgaCBpbiBiJyBgc2VxYCBmb2xkTGVmdCBmIGInIHQNCiANCnJlZHVjZVJpZ2h0IDo6IChhIC0+IGEgLT4gYSkgLT4gTGlzdCBhIC0+IGENCnJlZHVjZVJpZ2h0IF8gTmlsID0gZXJyb3IgImJ6enQuIHJlZHVjZVJpZ2h0IG9uIGVtcHR5IGxpc3QiDQpyZWR1Y2VSaWdodCBmIChDb25zIGggdCkgPSBmb2xkUmlnaHQgZiBoIHQNCiANCnJlZHVjZUxlZnQgOjogKGEgLT4gYSAtPiBhKSAtPiBMaXN0IGEgLT4gYQ0KcmVkdWNlTGVmdCBfIE5pbCA9IGVycm9yICJienp0LiByZWR1Y2VMZWZ0IG9uIGVtcHR5IGxpc3QiDQpyZWR1Y2VMZWZ0IGYgKENvbnMgaCB0KSA9IGZvbGRMZWZ0IGYgaCB0DQogDQotLSBFTkQgSGVscGVyIGZ1bmN0aW9ucyBhbmQgZGF0YSB0eXBlcw0KIA0KLS0gQkVHSU4gRXhlcmNpc2VzDQogDQotLSBFeGVyY2lzZSAxDQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAxDQotLSBDb3JyZWN0bmVzczogMi4wIG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMC41IG1hcmsNCi0tIEVsZWdhbmNlOiAwLjUgbWFya3MNCi0tIFRvdGFsOiAzDQphZGQgCQkJOjogTmF0dXJhbCAtPiBOYXR1cmFsIC0+IE5hdHVyYWwNCmFkZCB4IFplcm8JCT0geA0KYWRkIHggeSAJCT0gc3VjYyAoYWRkIHggKHByZWQgeSkpDQogDQotLSBFeGVyY2lzZSAyDQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAyDQotLSBDb3JyZWN0bmVzczogMi41IG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMSBtYXJrDQotLSBFbGVnYW5jZTogMC41IG1hcmtzDQotLSBUb3RhbDogNA0Kc3VtIAkJCTo6IExpc3QgSW50IC0+IEludA0Kc3VtIAkJCT0gZm9sZFJpZ2h0ICgrKSAwIA0KIA0KLS0gRXhlcmNpc2UgMw0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogMg0KLS0gQ29ycmVjdG5lc3M6IDIuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEgbWFyaw0KLS0gRWxlZ2FuY2U6IDAuNSBtYXJrcw0KLS0gVG90YWw6IDQNCmxlbmd0aCAJCQk6OiBMaXN0IGEgLT4gSW50DQpsZW5ndGggCQkJPSBmb2xkUmlnaHQgKFxfIHkgLT4gMSArIHkpIDANCiANCi0tIEV4ZXJjaXNlIDQNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDUNCi0tIENvcnJlY3RuZXNzOiA0LjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxLjAgbWFyaw0KLS0gRWxlZ2FuY2U6IDEuNSBtYXJrcw0KLS0gVG90YWw6IDcNCm1hcCAJCQk6OiAoYSAtPiBiKSAtPiBMaXN0IGEgLT4gTGlzdCBiDQptYXAgZgkJCT0gZm9sZFJpZ2h0IChceCB5IC0+IENvbnMgKGYgeCkgeSkgTmlsDQogDQotLSBFeGVyY2lzZSA1DQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA1DQotLSBDb3JyZWN0bmVzczogNC41IG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMS41IG1hcmtzDQotLSBFbGVnYW5jZTogMSBtYXJrDQotLSBUb3RhbDogNw0KZmlsdGVyIAkJCTo6IChhIC0+IEJvb2wpIC0+IExpc3QgYSAtPiBMaXN0IGENCmZpbHRlciBwCQk9IGZvbGRSaWdodCAoXHggeSAtPiBpZiBwIHggDQoJCQkJCQkJCSAgICAgdGhlbiBDb25zIHggeSANCgkJCQkJCQkJICAgICBlbHNlIHkNCgkJCQkJCQkJICAgICApIE5pbA0KIA0KLS0gRXhlcmNpc2UgNg0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogNQ0KLS0gQ29ycmVjdG5lc3M6IDQuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEuNSBtYXJrcw0KLS0gRWxlZ2FuY2U6IDEgbWFyaw0KLS0gVG90YWw6IDcNCmFwcGVuZCAJCQk6OiBMaXN0IGEgLT4gTGlzdCBhIC0+IExpc3QgYQ0KYXBwZW5kIHhzIHlzIAk9IGZvbGRSaWdodCBDb25zIHlzIHhzDQoNCg0KLS0gRXhlcmNpc2UgNw0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogNQ0KLS0gQ29ycmVjdG5lc3M6IDQuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEuNSBtYXJrcw0KLS0gRWxlZ2FuY2U6IDEgbWFyaw0KLS0gVG90YWw6IDcNCmZsYXR0ZW4gCQk6OiBMaXN0IChMaXN0IGEpIC0+IExpc3QgYQ0KZmxhdHRlbiAJCT0gZm9sZFJpZ2h0IGFwcGVuZCBOaWwNCiANCi0tIEV4ZXJjaXNlIDgNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDcNCi0tIENvcnJlY3RuZXNzOiA1LjAgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxLjUgbWFya3MNCi0tIEVsZWdhbmNlOiAxLjUgbWFyaw0KLS0gVG90YWw6IDgNCmZsYXRNYXAgCQk6OiBMaXN0IGEgLT4gKGEgLT4gTGlzdCBiKSAtPiBMaXN0IGINCmZsYXRNYXAgeHMgZiAJPSBmbGF0dGVuIChtYXAgZiB4cykNCiANCi0tIEV4ZXJjaXNlIDkNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDgNCi0tIENvcnJlY3RuZXNzOiAzLjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAzLjAgbWFya3MNCi0tIEVsZWdhbmNlOiAyLjUgbWFya3MNCi0tIFRvdGFsOiA5DQptYXhpbXVtIAkJOjogTGlzdCBJbnQgLT4gSW50DQptYXhpbXVtIAkJPSByZWR1Y2VSaWdodCBtYXgNCiANCi0tIEV4ZXJjaXNlIDEwDQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAxMA0KLS0gQ29ycmVjdG5lc3M6IDUuMCBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDIuNSBtYXJrcw0KLS0gRWxlZ2FuY2U6IDIuNSBtYXJrcw0KLS0gVG90YWw6IDEwDQpyZXZlcnNlIAkJOjogTGlzdCBhIC0+IExpc3QgYQ0KcmV2ZXJzZSAJCT0gZm9sZExlZnQgKFx4IHkgLT4gQ29ucyB5IHgpIE5pbA0KIA0KLS0gRU5EIEV4ZXJjaXNlcw0KIA0KLS0gQkVHSU4gVGVzdHMgZm9yIEV4ZXJjaXNlcw0KIA0KbWFpbiA6OiBJTyAoKQ0KbWFpbiA9DQogIGxldCBzaG93TmlsID0gc2hvdyAoTmlsIDo6IExpc3QgSW50KQ0KICAgICAgcmVzdWx0cyA9DQogICAgICAgIFsNCiAgICAgICAgLS0gYWRkDQogICAgICAgICgiYWRkIiwNCiAgICAgICAgIHNob3cgKGFkZCBvbmUgdHdvKQ0KICAgICAgICwgc2hvdyB0aHJlZSksDQogDQogICAgICAgICgiYWRkIiwNCiAgICAgICAgIHNob3cgKGFkZCBaZXJvIHR3bykNCiAgICAgICAsIHNob3cgdHdvKSwNCiANCiAgICAgICAgLS0gc3VtDQogICAgICAgICgic3VtIiwNCiAgICAgICAgIHNob3cgKHN1bSAoQ29ucyAxIChDb25zIDIgKENvbnMgMyBOaWwpKSkpDQogICAgICAgLCBzaG93IDYpLA0KIA0KICAgICAgICAoInN1bSIsDQogICAgICAgICBzaG93IChzdW0gTmlsKQ0KICAgICAgICwgc2hvdyAwKSwNCiANCiAgICAgICAgLS0gbGVuZ3RoDQogICAgICAgICgibGVuZ3RoIiwNCiAgICAgICAgIHNob3cgKGxlbmd0aCAoQ29ucyAnYScgKENvbnMgJ2InIChDb25zICdjJyBOaWwpKSkpDQogICAgICAgLCBzaG93IDMpLA0KIA0KICAgICAgICAoImxlbmd0aCIsDQogICAgICAgICBzaG93IChsZW5ndGggTmlsKQ0KICAgICAgICwgc2hvdyAwKSwNCiANCiAgICAgICAgLS0gbWFwDQogICAgICAgICgibWFwIiwNCiAgICAgICAgIHNob3cgKG1hcCAoKzEpIChDb25zIDEgKENvbnMgMiAoQ29ucyAzIE5pbCkpKSkNCiAgICAgICAsIHNob3cgKENvbnMgMiAoQ29ucyAzIChDb25zIDQgTmlsKSkpKSwNCiANCiAgICAgICAgKCJtYXAiLA0KICAgICAgICAgc2hvdyAobWFwICgrMSkgTmlsKQ0KICAgICAgICwgc2hvd05pbCksDQogDQogICAgICAgIC0tIGZpbHRlcg0KICAgICAgICAoImZpbHRlciIsDQogICAgICAgICBzaG93IChmaWx0ZXIgZXZlbiAoQ29ucyAxIChDb25zIDIgKENvbnMgMyBOaWwpKSkpDQogICAgICAgLCBzaG93IChDb25zIDIgTmlsKSksDQogDQogICAgICAgICgiZmlsdGVyIiwNCiAgICAgICAgIHNob3cgKGZpbHRlciBldmVuIE5pbCkNCiAgICAgICAsIHNob3dOaWwpLA0KIA0KICAgICAgICAtLSBhcHBlbmQNCiAgICAgICAgKCJhcHBlbmQiLA0KICAgICAgICAgc2hvdyAoYXBwZW5kIChDb25zIDEgKENvbnMgMiAoQ29ucyAzIE5pbCkpKSAoQ29ucyA0IE5pbCkpDQogICAgICAgLCBzaG93IChDb25zIDEgKENvbnMgMiAoQ29ucyAzIChDb25zIDQgTmlsKSkpKSksDQogDQogICAgICAgICgiYXBwZW5kIiwNCiAgICAgICAgIHNob3cgKGFwcGVuZCAoQ29ucyAxIChDb25zIDIgKENvbnMgMyBOaWwpKSkgTmlsKQ0KICAgICAgICwgc2hvdyAoQ29ucyAxIChDb25zIDIgKENvbnMgMyBOaWwpKSkpLA0KIA0KICAgICAgICAtLSBmbGF0dGVuDQogICAgICAgICgiZmxhdHRlbiIsDQogICAgICAgICBzaG93IChmbGF0dGVuIChDb25zIChDb25zIDEgKENvbnMgMiBOaWwpKSAoQ29ucyAoQ29ucyAzIChDb25zIDQgTmlsKSkgTmlsKSkpDQogICAgICAgLCBzaG93IChDb25zIDEgKENvbnMgMiAoQ29ucyAzIChDb25zIDQgTmlsKSkpKSksDQogDQogICAgICAgIC0tIGZsYXRNYXANCiAgICAgICAgKCJmbGF0TWFwIiwNCiAgICAgICAgIHNob3cgKGZsYXRNYXAgKENvbnMgMSAoQ29ucyAyIChDb25zIDMgTmlsKSkpIChcbiAtPiBDb25zIChuKzEpIChDb25zIChuKzIpIE5pbCkpKQ0KICAgICAgICwgc2hvdyAoQ29ucyAyIChDb25zIDMgKENvbnMgMyAoQ29ucyA0IChDb25zIDQgKENvbnMgNSBOaWwpKSkpKSkpLA0KIA0KICAgICAgICAtLSBtYXhpbXVtDQogICAgICAgICgibWF4aW11bSIsDQogICAgICAgICBzaG93IChtYXhpbXVtIChDb25zIDMgKENvbnMgMSAoQ29ucyAyIE5pbCkpKSkNCiAgICAgICAsIHNob3cgMyksDQogDQogICAgICAgIC0tIHJldmVyc2UNCiAgICAgICAgKCJyZXZlcnNlIiwNCiAgICAgICAgIHNob3cgKHJldmVyc2UgKENvbnMgMSAoQ29ucyAyIChDb25zIDMgTmlsKSkpKQ0KICAgICAgICwgc2hvdyAoQ29ucyAzIChDb25zIDIgKENvbnMgMSBOaWwpKSkpDQogICAgICAgIF0NCiAgICAgIGNoZWNrIChuLCBhLCBiKSA9IGRvIHByaW50ICgiPT09ICIgKysgbiArKyAiID09PSIpDQogICAgICAgICAgICAgICAgICAgICAgICAgICBwcmludCAoaWYgYSA9PSBiIHRoZW4gIlBBU1MiIGVsc2UgIkZBSUwgRXhwZWN0ZWQ6ICIgKysgYiArKyAiIEFjdHVhbDogIiArKyBhKQ0KIA0KICBpbiBtYXBNXyBjaGVjayByZXN1bHRzDQogDQotLSBFTkQgVGVzdHMgZm9yIEV4ZXJjaXNlcw==
September 3rd, 2010 at 11:22 pm
Oh, and that was solely the exercises, in a base64 encoded gzip file.