## FSA Lab, Week 1

``> module FSAlab1 where``

Exercises with `foldr` and `foldl`

The `foldr` function is defined by

`````` foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f b [] = b
foldr f b (x:xs) = f x (foldr f b xs)``````

This gives the abstract pattern of recursion over lists, and it can be used to give abstract definitions of many functions that operate on lists. Example:

`` and = foldr (&&) True.``

Define `length` in terms of `foldr`.

Define `elem x` in terms of `foldr`.

Define `or` in terms of `foldr`.

Define `map f` in terms of `foldr`.

Define `filter p` in terms of `foldr`.

Define `(++)` in terms of `foldr`.

Define `reverse` in terms of `foldr`.

The function `foldr` folds to the right. It is also possible to fold to the left, by means of:

`````` foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs``````

Give an alternative definition of `reverse`, in terms of `foldl`.

Which of the two versions of reverse is more efficient? Why?

One of `foldr`, `foldl` may work on infinite lists. Which one? Why?

Look up some explanations on wiki.haskell.org.

Implement and use the Luhn Algorithm.

The Luhn algorithm is a formula for validating credit card numbers.

Give an implementation in Haskell. The type declaration should run:

``luhn :: Integer -> Bool``

This function should check whether an input number satisfies the Luhn formula.

Next, use `luhn` to write functions

``isAmericanExpress, isMaster, isVisa :: Integer -> Bool``

for checking whether an input number is a valid American Express Card, Master Card, or Visa Card number. Consult Wikipedia for the relevant properties.

Crime Scene Investigation

A group of five school children is caught in a crime. One of them has stolen something from some kid they all dislike. The headmistress has to find out who did it. She questions the children, and this is what they say:

Matthew: Carl didnâ€™t do it, and neither did I.

Peter: It was Matthew or it was Jack.

Jack: Matthew and Peter are both lying.

Arnold: Matthew or Peter is speaking the truth, but not both.

Carl: What Arnold says is not true.

Their class teacher now comes in. She says: three of these boys always tell the truth, and two always lie. You can assume that what the class teacher says is true. Use Haskell to write a function that computes who was the thief, and a function that computes which boys made honest declarations. Here are some definitions to get you started.

``````> data Boy = Matthew | Peter | Jack | Arnold | Carl
>            deriving (Eq,Show)
>
> boys = [Matthew, Peter, Jack, Arnold, Carl]``````

You should first define a function

``accuses :: Boy -> Boy -> Bool``

for encoding whether a boy accuses another boy.

Next, define

``accusers :: Boy -> [Boy]``

giving the list of accusers of each boy.

Finally, define

``guilty, honest :: [Boy]``

to give the list of guilty boys, plus the list of boys who made honest (true) statements.

If the puzzle is well-designed, then guilty should give a singleton list.

Hint: the puzzle is well-designed.

Know Thyself

If this was all difficult for you, go back to the exercises in the first two chapters of The Haskell Road and do the implementation exercises.

Bonus

If this was all easy for you, you should next try some of the problems of Project Euler. Try problems 9, 10 and 49.

Submission deadline: Sunday, Sept 11, at midnight.

But: make sure that you have some work to discuss for the Friday code review session.