λ Tony’s blog λ

{-
The 'Scala exercises for beginners' set rules about what you were not permitted to use.
This is because you were permitted to use some functions, but not others. This led to
some amount of confusion (sorry). Instead, this time, I will define my own data types.
One is equivalent to Haskell's list [], although without the syntactic support and the
other is the set of natural numbers (0 onward). I will also predefine some useful
functions that you might consider using to solve each problem. That way, I needn't set
any rules; you are very much free to do what you want (Although, converting between
this type and [] is considered cheating, as you might expect ;).
 
I will consider converting the Scala exercises to use a similar strategy in a second
revision to prevent this confusion.
 
TOTAL marks:    /66
-}
 
module Exercises where
 
import Prelude hiding (sum, length, map, filter, maximum, reverse, succ, pred)
 
-- The custom list type
data List t = Nil | Cons t (List t)
 
instance (Show t) => Show (List t) where
  show = show . toList
    where
    -- unfoldr, but let's not import Data.List
    toList Nil = []
    toList (Cons h t) = h : toList t
 
-- the custom numeric type
data Natural = Zero | Succ Natural
one = Succ Zero
two = Succ one
 
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
 
unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f b = case f b of Just (a, b') -> a `Cons` unfold f b'
                         Nothing -> Nil
 
-- 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"

9 Responses to “Haskell exercises for beginners”

1. jeff Heon Says:
   July 18th, 2008 at 2:27 am

   Damn you!

   Now I’ll eventually have to learn Haskell just to do the exercises and see how it compares with Scala

2. Geoff Reedy Says:
   July 18th, 2008 at 3:54 am

   I’m not necessarily a beginner, but I’ve never actually applied the universality of fold before. It was kind of fun figuring it all out. It’s just the part after ‘– Exercises’ gzip’d and base64′d:

   H4sIAIBwb0UAA71VTW/bMAy9+1fw0IONLkU+l9TAdmi3Ahu6YOh6GnpRbDkRJluBJHfOvx+l2I5V
   W10HDMkhtkhKfu+RFEcj+FxRmTBFVRCMTiuYmNUD5USzZwqfWJaxpOT6EB89t0JKmuiCKhXD9GoM
   OZG/lPF8pzITMidFQmMYXy2sxx7N6da12vhHoQmPYRaQNIU4hjXRpSQcRh8HXm0QgQ18gEzw9IFt
   dxrCiwgtYVkYExB1VxYKSBQA/N5RSfEJjfUnlQL3roXesWLb9YQ/yiSBKkLv11Lp4/odGlxZpl5Z
   pgOyLDyyTN4oyjxQZW5EuWcI6UuhjRT4sOZKuSpcRjBGo4t3dma8nBZbvWshkwZwbW8×39MMIT9V
   cDAR1eVkCPzcC37RAz/3g6+r04U/GYC/DHKyN9hDi3sTmf8TD/u2sTFZT31DRZmoW2GqKTOldFAR
   rBnv8Vr8J14dT4dYS7ZllTGuqTwRuxGCD3EjTeQr9BKCBNAPIrPt87ffoyxpK4s55E277ghXdptP
   wvdnlpDs97RI3bruqVcHoXYHVz5LHm0vWSzPXQj4JU2LlkZ4BB51K6AOQficYaHj8hsWPEtd5Csv
   8mUP+cI7HnzIO1Ojxr4KGiROCsJOY0adHm2CMRWZk4k6RaakLqDpZJfatZfaqkdt5k3KrEv6RG06
   cO1c45VSsXz4pm9cvW40Aeg0PRVBmLPiRpTHCsVtEbyY5mP/OB//Q8KmwwkbYoXnSvpMJX59oGta
   X3cc2IozvWJ7PvgD7eqYPJ0IAAA=

3. web design Says:
   July 19th, 2008 at 2:36 am

   shouldn’t sum and length work over Naturals instead of Ints? now, Haskell exercises for intermediate programmers - same thing but in haskell’s type system.

4. Ben Ellis Says:
   July 19th, 2008 at 5:52 am

   Wonderful stuff. Reimplementing language basics in terms of the most minimal functions always seems to give me extra grounding in how I ought to program functionally and what actually goes on under the hood. I probably don’t count as a Haskell beginner (I did a similar exercise with rewriting the functions in Control.Monad to get a better feel for them) but I enjoyed it.

5. Garrett Rowe Says:
   July 19th, 2008 at 5:37 pm

   I agree with web design, were we supposed to convert from a List Int to a List Natural to use the add function? If so, I guess you’ll have to deduct points from me. Be that as it may, I want my cookies!

   bW9kdWxlIEV4ZXJjaXNlcyB3aGVyZQ0KDQppbXBvcnQgUHJlbHVkZSBoaWRpbmcgKHN1bSwgbGVuZ3RoLCBtYXAsIGZpbHRlciwgbWF4aW11bSwgcmV2ZXJzZSwgc3VjYywgcHJlZCkNCg0KLS0gVGhlIGN1c3RvbSBsaXN0IHR5cGUNCmRhdGEgTGlzdCB0ID0gTmlsIHwgQ29ucyB0IChMaXN0IHQpDQoNCmluc3RhbmNlIChTaG93IHQpID0+IFNob3cgKExpc3QgdCkgd2hlcmUNCiAgc2hvdyA9IHNob3cgLiB0b0xpc3QNCiAgICB3aGVyZQ0KICAgIC0tIHVuZm9sZHIsIGJ1dCBsZXRcJ3Mgbm90IGltcG9ydCBEYXRhLkxpc3QNCiAgICB0b0xpc3QgTmlsID0gW10NCiAgICB0b0xpc3QgKENvbnMgaCB0KSA9IGggOiB0b0xpc3QgdA0KDQotLSB0aGUgY3VzdG9tIG51bWVyaWMgdHlwZQ0KZGF0YSBOYXR1cmFsID0gWmVybyB8IFN1Y2MgTmF0dXJhbA0Kb25lID0gU3VjYyBaZXJvDQp0d28gPSBTdWNjIG9uZQ0KDQppbnN0YW5jZSBTaG93IE5hdHVyYWwgd2hlcmUNCiAgc2hvdyA9IHNob3cgLiB0b0ludA0KICAgIHdoZXJlDQogICAgdG9JbnQgWmVybyA9IDANCiAgICB0b0ludCAoU3VjYyB4KSA9IDEgKyB0b0ludCB4DQoNCi0tIGZ1bmN0aW9ucyBvdmVyIE5hdHVyYWwgdGhhdCB5b3UgbWF5IGNvbnNpZGVyIHVzaW5nDQpzdWNjIDo6IE5hdHVyYWwgLT4gTmF0dXJhbA0Kc3VjYyA9IFN1Y2MNCg0KcHJlZCA6OiBOYXR1cmFsIC0+IE5hdHVyYWwNCnByZWQgWmVybyA9IGVycm9yIFwiYnp6dC4gWmVybyBoYXMgbm8gcHJlZGVjZXNzb3IgaW4gbmF0dXJhbHNcIg0KcHJlZCAoU3VjYyB4KSA9IHgNCg0KLS0gZnVuY3Rpb25zIG92ZXIgTGlzdCB0aGF0IHlvdSBtYXkgY29uc2lkZXIgdXNpbmcNCmZvbGRSaWdodCA6OiAoYSAtPiBiIC0+IGIpIC0+IGIgLT4gTGlzdCBhIC0+IGINCmZvbGRSaWdodCBfIGIgTmlsID0gYg0KZm9sZFJpZ2h0IGYgYiAoQ29ucyBoIHQpID0gZiBoIChmb2xkUmlnaHQgZiBiIHQpDQoNCmZvbGRMZWZ0IDo6IChiIC0+IGEgLT4gYikgLT4gYiAtPiBMaXN0IGEgLT4gYg0KZm9sZExlZnQgXyBiIE5pbCA9IGINCmZvbGRMZWZ0IGYgYiAoQ29ucyBoIHQpID0gbGV0IGJcJyA9IGYgYiBoIGluIGJcJyBgc2VxYCBmb2xkTGVmdCBmIGJcJyB0DQoNCnJlZHVjZVJpZ2h0IDo6IChhIC0+IGEgLT4gYSkgLT4gTGlzdCBhIC0+IGENCnJlZHVjZVJpZ2h0IF8gTmlsID0gZXJyb3IgXCJienp0LiByZWR1Y2VSaWdodCBvbiBlbXB0eSBsaXN0XCINCnJlZHVjZVJpZ2h0IGYgKENvbnMgaCB0KSA9IGZvbGRSaWdodCBmIGggdA0KDQpyZWR1Y2VMZWZ0IDo6IChhIC0+IGEgLT4gYSkgLT4gTGlzdCBhIC0+IGENCnJlZHVjZUxlZnQgXyBOaWwgPSBlcnJvciBcImJ6enQuIHJlZHVjZUxlZnQgb24gZW1wdHkgbGlzdFwiDQpyZWR1Y2VMZWZ0IGYgKENvbnMgaCB0KSA9IGZvbGRMZWZ0IGYgaCB0DQoNCnVuZm9sZCA6OiAoYiAtPiBNYXliZSAoYSwgYikpIC0+IGIgLT4gTGlzdCBhDQp1bmZvbGQgZiBiID0gY2FzZSBmIGIgb2YgSnVzdCAoYSwgYlwnKSAtPiBhIGBDb25zYCB1bmZvbGQgZiBiXCcNCiAgICAgICAgICAgICAgICAgICAgICAgICBOb3RoaW5nIC0+IE5pbA0KDQotLSBFeGVyY2lzZXMNCg0KLS0gRXhlcmNpc2UgMQ0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogMQ0KLS0gQ29ycmVjdG5lc3M6IDIuMCBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDAuNSBtYXJrDQotLSBFbGVnYW5jZTogMC41IG1hcmtzDQotLSBUb3RhbDogMw0KYWRkIDo6IE5hdHVyYWwgLT4gTmF0dXJhbCAtPiBOYXR1cmFsDQphZGQgeCB5ID0gY2FzZSB4IG9mDQogICAgICAgICAgICAgWmVybyAtPiB5DQogICAgICAgICAgICAgXyAgICAtPiBhZGQgKHByZWQgeCkgKHN1Y2MgeSkNCg0KLS0gRXhlcmNpc2UgMg0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogMg0KLS0gQ29ycmVjdG5lc3M6IDIuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEgbWFyaw0KLS0gRWxlZ2FuY2U6IDAuNSBtYXJrcw0KLS0gVG90YWw6IDQNCnN1bSA6OiBMaXN0IEludCAtPiBJbnQNCnN1bSA9IGZvbGRMZWZ0ICgrKSAwDQoNCi0tIEV4ZXJjaXNlIDMNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDINCi0tIENvcnJlY3RuZXNzOiAyLjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxIG1hcmsNCi0tIEVsZWdhbmNlOiAwLjUgbWFya3MNCi0tIFRvdGFsOiA0DQpsZW5ndGggOjogTGlzdCBhIC0+IEludA0KbGVuZ3RoID0gZm9sZExlZnQgKFxceCBfIC0+IHggKyAxKSAwDQoNCi0tIEV4ZXJjaXNlIDQNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDUNCi0tIENvcnJlY3RuZXNzOiA0LjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxLjAgbWFyaw0KLS0gRWxlZ2FuY2U6IDEuNSBtYXJrcw0KLS0gVG90YWw6IDcNCm1hcCA6OiAoYSAtPiBiKSAtPiBMaXN0IGEgLT4gTGlzdCBiDQptYXAgZiA9IGZvbGRSaWdodCAoXFxhIGIgLT4gKGYgYSkgYENvbnNgIGIpIE5pbA0KDQotLSBFeGVyY2lzZSA1DQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA1DQotLSBDb3JyZWN0bmVzczogNC41IG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMS41IG1hcmtzDQotLSBFbGVnYW5jZTogMSBtYXJrDQotLSBUb3RhbDogNw0KZmlsdGVyIDo6IChhIC0+IEJvb2wpIC0+IExpc3QgYSAtPiBMaXN0IGENCmZpbHRlciBwID0gZm9sZFJpZ2h0IChcXGEgYiAtPiBpZiBwIGEgdGhlbiBhIGBDb25zYCBiIGVsc2UgYikgTmlsDQoNCi0tIEV4ZXJjaXNlIDYNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDUNCi0tIENvcnJlY3RuZXNzOiA0LjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxLjUgbWFya3MNCi0tIEVsZWdhbmNlOiAxIG1hcmsNCi0tIFRvdGFsOiA3DQphcHBlbmQgOjogTGlzdCBhIC0+IExpc3QgYSAtPiBMaXN0IGENCmFwcGVuZCB4cyB5cyA9IGZvbGRSaWdodCAoXFxhIGIgLT4gYSBgQ29uc2AgYikgeXMgeHMNCg0KLS0gRXhlcmNpc2UgNw0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogNQ0KLS0gQ29ycmVjdG5lc3M6IDQuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEuNSBtYXJrcw0KLS0gRWxlZ2FuY2U6IDEgbWFyaw0KLS0gVG90YWw6IDcNCmZsYXR0ZW4gOjogTGlzdCAoTGlzdCBhKSAtPiBMaXN0IGENCmZsYXR0ZW4gPSBmb2xkUmlnaHQgKFxcYSBiIC0+IGFwcGVuZCBhIGIpIE5pbA0KDQotLSBFeGVyY2lzZSA4DQotLSBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA3DQotLSBDb3JyZWN0bmVzczogNS4wIG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMS41IG1hcmtzDQotLSBFbGVnYW5jZTogMS41IG1hcmsNCi0tIFRvdGFsOiA4DQpmbGF0TWFwIDo6IExpc3QgYSAtPiAoYSAtPiBMaXN0IGIpIC0+IExpc3QgYg0KZmxhdE1hcCB4cyBmID0gZmxhdHRlbiAuIG1hcCBmICQgeHMNCg0KLS0gRXhlcmNpc2UgOQ0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogOA0KLS0gQ29ycmVjdG5lc3M6IDMuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDMuMCBtYXJrcw0KLS0gRWxlZ2FuY2U6IDIuNSBtYXJrcw0KLS0gVG90YWw6IDkNCm1heGltdW0gOjogTGlzdCBJbnQgLT4gSW50DQptYXhpbXVtID0gcmVkdWNlTGVmdCBtYXgNCg0KLS0gRXhlcmNpc2UgMTANCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDEwDQotLSBDb3JyZWN0bmVzczogNS4wIG1hcmtzDQotLSBQZXJmb3JtYW5jZTogMi41IG1hcmtzDQotLSBFbGVnYW5jZTogMi41IG1hcmtzDQotLSBUb3RhbDogMTANCnJldmVyc2UgOjogTGlzdCBhIC0+IExpc3QgYQ0KcmV2ZXJzZSA9IGZvbGRMZWZ0IChcXGwgYSAtPiBhIGBDb25zYCBsKSBOaWw=

6. Garrett Rowe Says:
   July 19th, 2008 at 5:52 pm

   Just in case… (I can’t jeopardize my reward)

   LS0gRXhlcmNpc2UgMg0KLS0gUmVsYXRpdmUgRGlmZmljdWx0eTogMg0KLS0gQ29ycmVjdG5lc3M6IDIuNSBtYXJrcw0KLS0gUGVyZm9ybWFuY2U6IDEgbWFyaw0KLS0gRWxlZ2FuY2U6IDAuNSBtYXJrcw0KLS0gVG90YWw6IDQNCi0tc3VtIDo6IExpc3QgSW50IC0+IEludA0KLS1zdW0gPSBmb2xkTGVmdCAoKykgMA0KDQpzdW0gOjogTGlzdCBOYXR1cmFsIC0+IE5hdHVyYWwNCnN1bSA9IGZvbGRMZWZ0IGFkZCBaZXJvDQoNCi0tIEV4ZXJjaXNlIDMNCi0tIFJlbGF0aXZlIERpZmZpY3VsdHk6IDINCi0tIENvcnJlY3RuZXNzOiAyLjUgbWFya3MNCi0tIFBlcmZvcm1hbmNlOiAxIG1hcmsNCi0tIEVsZWdhbmNlOiAwLjUgbWFya3MNCi0tIFRvdGFsOiA0DQotLWxlbmd0aCA6OiBMaXN0IGEgLT4gSW50DQotLWxlbmd0aCA9IGZvbGRMZWZ0IChcXHggXyAtPiB4ICsgMSkgMA0KDQpsZW5ndGggOjogTGlzdCBhIC0+IE5hdHVyYWwNCmxlbmd0aCA9IGZvbGRMZWZ0IChcXHggXyAtPiBzdWNjIHgpIFplcm8NCg==

7. jeff Heon Says:
   July 22nd, 2008 at 3:13 am

   Hello Tony,

   I did have a look at Haskell, and it has been very informative for me!

   Now I see in Scala where pattern matching comes from and why the list matching examples in the Scala books have the form x:xs.

   I see Haskell is a highly mathematical language. Once I get through the tutorials (Haskell-Tutorial and A Gentle Introduction to Haskell 98), I’ll give the Haskell exercises a shot
   So far the tutorials have made me realize I was putting an unnecessary step in my list recursive functions, so I am already a better programmer for brushing on Haskell

8. Tony Morris Says:
   July 22nd, 2008 at 4:55 am

   Great to hear Jeff, keep it up
   To everyone who has submitted their answer here or email (for Scala or Haskell), I plan to give an examination of the possible solutions and critique them.

   At the moment, I am preparing a Scala talk for a Java User’s Group, so hopefully I will get a moment after that!

9. Geoff Reedy Says:
   July 22nd, 2008 at 7:27 am

   Are you going to evaluate the haskell solutions for proper lazyness? That is, you can take the head of map, filter, etc. of an infinite list?

   For example, given:

   > from :: Int -> List Int
   > from n = Cons n $ from (n+1)
   >
   > take n :: Int -> List a -> List a
   > take n _ | n take _ Nil = Nil
   > take n (Cons x xs) = Cons x $ take (n-1) xs

   then

   > take 5 $ map (*2) $ from 1

   should evaluate to

   > Cons 2 $ Cons 4 $ Cons 6 $ Cons 8 $ Cons 10 Nil

   not bottom.

Leave a Reply