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

RossPaterson (talk | contribs) m (whitespace only) |
m (→Problem 8) |
||

(25 intermediate revisions by 15 users not shown) | |||

Line 1: | Line 1: | ||

__NOTOC__ | __NOTOC__ | ||

− | This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https:// | + | This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://sites.google.com/site/prologsite/prolog-problems Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems]. |

− | |||

− | |||

== Problem 1 == | == Problem 1 == | ||

Line 9: | Line 7: | ||

(*) Find the last element of a list. | (*) Find the last element of a list. | ||

− | (Note | + | (Note that the Lisp transcription of this problem is incorrect.) |

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

<haskell> | <haskell> | ||

− | + | λ> myLast [1,2,3,4] | |

4 | 4 | ||

− | + | λ> myLast ['x','y','z'] | |

'z' | 'z' | ||

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

− | + | [[99 questions/Solutions/1 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 2 == | == Problem 2 == | ||

Line 39: | Line 25: | ||

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

− | (Note | + | (Note that the Lisp transcription of this problem is incorrect.) |

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

<haskell> | <haskell> | ||

− | + | λ> myButLast [1,2,3,4] | |

3 | 3 | ||

− | + | λ> myButLast ['a'..'z'] | |

'y' | 'y' | ||

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

− | Solutions | + | [[99 questions/Solutions/2 | Solutions]] |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 3 == | == Problem 3 == | ||

Line 71: | Line 47: | ||

<pre> | <pre> | ||

* (element-at '(a b c d e) 3) | * (element-at '(a b c d e) 3) | ||

− | + | c | |

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

Line 77: | Line 53: | ||

<haskell> | <haskell> | ||

− | + | λ> elementAt [1,2,3] 2 | |

2 | 2 | ||

− | + | λ> elementAt "haskell" 5 | |

'e' | 'e' | ||

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

− | + | [[99 questions/Solutions/3 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 4 == | == Problem 4 == | ||

Line 107: | Line 69: | ||

<haskell> | <haskell> | ||

− | + | λ> myLength [123, 456, 789] | |

3 | 3 | ||

− | + | λ> myLength "Hello, world!" | |

13 | 13 | ||

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

− | + | [[99 questions/Solutions/4 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 5 == | == Problem 5 == | ||

Line 130: | Line 85: | ||

<haskell> | <haskell> | ||

− | + | λ> myReverse "A man, a plan, a canal, panama!" | |

"!amanap ,lanac a ,nalp a ,nam A" | "!amanap ,lanac a ,nalp a ,nam A" | ||

− | + | λ> myReverse [1,2,3,4] | |

[4,3,2,1] | [4,3,2,1] | ||

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

− | + | [[99 questions/Solutions/5 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 6 == | == Problem 6 == | ||

Line 168: | Line 101: | ||

<haskell> | <haskell> | ||

− | + | λ> isPalindrome [1,2,3] | |

False | False | ||

− | + | λ> isPalindrome "madamimadam" | |

True | True | ||

− | + | λ> isPalindrome [1,2,4,8,16,8,4,2,1] | |

True | True | ||

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

− | + | [[99 questions/Solutions/6 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

== Problem 7 == | == Problem 7 == | ||

Line 198: | Line 127: | ||

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

+ | We have to define a new data type, because lists in Haskell are homogeneous. | ||

<haskell> | <haskell> | ||

− | + | data NestedList a = Elem a | List [NestedList a] | |

+ | </haskell> | ||

+ | |||

+ | <haskell> | ||

+ | λ> flatten (Elem 5) | ||

[5] | [5] | ||

− | + | λ> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]]) | |

[1,2,3,4,5] | [1,2,3,4,5] | ||

− | + | λ> flatten (List []) | |

[] | [] | ||

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

− | |||

− | |||

− | |||

− | + | [[99 questions/Solutions/7 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 8 == | == Problem 8 == | ||

Line 229: | Line 150: | ||

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. | 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: | ||

<pre> | <pre> | ||

− | |||

* (compress '(a a a a b c c a a d e e e e)) | * (compress '(a a a a b c c a a d e e e e)) | ||

(A B C A D E) | (A B C A D E) | ||

+ | </pre> | ||

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

− | |||

− | |||

− | |||

− | |||

<haskell> | <haskell> | ||

− | compress | + | λ> compress "aaaabccaadeeee" |

− | + | "abcade" | |

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

− | + | [[99 questions/Solutions/8 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 9 == | == Problem 9 == | ||

Line 275: | Line 171: | ||

(**) Pack consecutive duplicates of list elements into sublists. | (**) Pack consecutive duplicates of list elements into sublists. | ||

If a list contains repeated elements they should be placed in separate sublists. | If a list contains repeated elements they should be placed in separate sublists. | ||

+ | |||

+ | Example: | ||

<pre> | <pre> | ||

− | |||

* (pack '(a a a a b c c a a d e e e e)) | * (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)) | ((A A A A) (B) (C C) (A A) (D) (E E E E)) | ||

− | < | + | </pre> |

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

− | |||

− | |||

− | |||

− | |||

<haskell> | <haskell> | ||

− | pack | + | λ> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', |

− | + | 'a', 'd', 'e', 'e', 'e', 'e'] | |

− | + | ["aaaa","b","cc","aa","d","eeee"] | |

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

− | + | [[99 questions/Solutions/9 | Solutions]] | |

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

Line 303: | Line 196: | ||

Example: | 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)) | |

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

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

− | < | + | <haskell> |

− | encode "aaaabccaadeeee" | + | λ> encode "aaaabccaadeeee" |

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

− | |||

− | |||

− | |||

− | |||

− | |||

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

− | + | [[99 questions/Solutions/10 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

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

## Latest revision as of 09:06, 9 February 2019

This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems and Ninety-Nine Lisp Problems.

## Problem 1

(*) Find the last element of a list.

(Note that the Lisp transcription of this problem is incorrect.)

Example in Haskell:

```
λ> myLast [1,2,3,4]
4
λ> myLast ['x','y','z']
'z'
```

## Problem 2

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

(Note that the Lisp transcription of this problem is incorrect.)

Example in Haskell:

```
λ> myButLast [1,2,3,4]
3
λ> myButLast ['a'..'z']
'y'
```

## 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

Example in Haskell:

```
λ> elementAt [1,2,3] 2
2
λ> elementAt "haskell" 5
'e'
```

## Problem 4

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

Example in Haskell:

```
λ> myLength [123, 456, 789]
3
λ> myLength "Hello, world!"
13
```

## Problem 5

(*) Reverse a list.

Example in Haskell:

```
λ> myReverse "A man, a plan, a canal, panama!"
"!amanap ,lanac a ,nalp a ,nam A"
λ> myReverse [1,2,3,4]
[4,3,2,1]
```

## 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).

Example in Haskell:

```
λ> isPalindrome [1,2,3]
False
λ> isPalindrome "madamimadam"
True
λ> isPalindrome [1,2,4,8,16,8,4,2,1]
True
```

## 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)

Example in Haskell:

We have to define a new data type, because lists in Haskell are homogeneous.

```
data NestedList a = Elem a | List [NestedList a]
```

```
λ> flatten (Elem 5)
[5]
λ> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
[1,2,3,4,5]
λ> 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:

```
λ> compress "aaaabccaadeeee"
"abcade"
```

## 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 Haskell:

```
λ> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a',
'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]
```

## 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))

Example in Haskell:

```
λ> encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]
```