# Difference between revisions of "99 questions/1 to 10"

KetilMalde (talk | contribs) (solution #9) |
KetilMalde (talk | contribs) (solution #10) |
||

Line 205: | Line 205: | ||

== Problem 10 == |
== Problem 10 == |
||

− | <Problem description> |
||

+ | (*) Run-length encoding of a list. |
||

+ | Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E. |
||

+ | Example: |
||

<pre> |
<pre> |
||

+ | * (encode '(a a a a b c c a a d e e e e)) |
||

+ | ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))<Problem description> |
||

+ | |||

Example: |
Example: |
||

<example in lisp> |
<example in lisp> |
||

Example in Haskell: |
Example in Haskell: |
||

− | <example in Haskell> |
||

+ | |||

+ | encode "aaaabccaadeeee" |
||

+ | [(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')] |
||

+ | |||

</pre> |
</pre> |
||

Solution: |
Solution: |
||

<haskell> |
<haskell> |
||

− | <solution in haskell> |
||

+ | encode xs = map \x -> (length x,head x) (group xs) |
||

</haskell> |
</haskell> |
||

− | |||

− | <description of implementation> |
||

[[Category:Tutorials]] |
[[Category:Tutorials]] |

## Revision as of 08:10, 12 December 2006

These are Haskell translations of Ninety Nine Lisp Problems.

If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.

## Problem 1

(*) Find the last box of a list.

Example:

* (my-last '(a b c d)) (D)

Example in Haskell:

```
Prelude> last [1,2,3,4]
4
Prelude> last ['x','y','z']
'z'
```

Solution:

```
last :: [a] -> a
last [x] = x
last (_:xs) = last xs
```

This function is defined in Prelude.

## Problem 2

(*) Find the last but one box of a list.

Example: * (my-but-last '(a b c d)) (C D)

This can be done by dropping all but the last two elements of a list:

```
myButLast :: [a] -> [a]
myButLast list = drop ((length list) - 2) list
```

## Problem 3

(*) Find the K'th element of a list. The first element in the list is number 1.

Example: * (element-at '(a b c d e) 3) C

This is (almost) the infix operator !! in Prelude, which is defined as:

```
(!!) :: [a] -> Int -> a
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
```

Except this doesn't quite work, because !! is zero-indexed, and element-at should be one-indexed. So:

```
elementAt :: [a] -> Int -> a
elementAt list i = list !! (i-1)
```

## Problem 4

(*) Find the number of elements of a list.

This is "length" in Prelude, which is defined as:

```
length :: [a] -> Int
length [] = 0
length (_:l) = 1 + length l
```

## Problem 5

(*) Reverse a list.

This is "reverse" in Prelude, which is defined as:

```
reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
```

The standard definition is concise, but not very readable. Another way to define reverse is:

```
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
```

## Problem 6

(*) Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).

This is trivial, because we can use reverse:

```
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == (reverse xs)
```

## Problem 7

(**) Flatten a nested list structure.

Transform a list, possibly holding lists as elements into a `flat' list by replacing each list with its elements (recursively).

Example: * (my-flatten '(a (b (c d) e))) (A B C D E)

This is tricky, because lists in Haskell are homogeneous. [1, [2, [3, 4], 5]] is a type error. We have to devise some way of represent a list that may (or may not) be nested:

```
data NestedList a = Elem a | List [NestedList a]
flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List []) = []
flatten (List (x:xs)) = flatten x ++ flatten (List xs)
```

Our NestedList datatype is either a single element of some type (Elem a), or a list of NestedLists of the same type. (List [NestedList a]). Let's try it out in ghci:

*Main> flatten (Elem 5) [5] *Main> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]]) [1,2,3,4,5] *Main> flatten (List []) []

## Problem 8

(**) Eliminate consecutive duplicates of list elements.

If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example: * (compress '(a a a a b c c a a d e e e e)) (A B C A D E) Example in Haskell: *Main> compress ['a','a','a','a','b','c','c','a','a','d','e','e','e','e'] ['a','b','c','a','d','e']

Solution:

```
compress = map head . group
```

We simply group equal values together (group), then take the head of each.

## Problem 9

(**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example: * (pack '(a a a a b c c a a d e e e e)) ((A A A A) (B) (C C) (A A) (D) (E E E E)) <example in lisp> Example in Haskell:

Solution:

```
group (x:xs) = let (first,rest) = span (==x) xs
in (x:first) : group rest
group [] = []
```

'group' is also in the Prelude, here's an implementation using 'span'.

## Problem 10

(*) Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

Example:

* (encode '(a a a a b c c a a d e e e e)) ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))<Problem description> Example: <example in lisp> Example in Haskell: encode "aaaabccaadeeee" [(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

Solution:

```
encode xs = map \x -> (length x,head x) (group xs)
```