99 questions/1 to 10
From HaskellWiki
Basvandijk (Talk  contribs) 
m (→Problem 7) 

(48 intermediate revisions by 25 users not shown)  
Line 1:  Line 1:  
__NOTOC__ 
__NOTOC__ 

−  These are Haskell translations of [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L99_NinetyNine_Lisp_Problems.html Ninety Nine Lisp Problems]. 
+  This is part of [[H99:_NinetyNine_Haskell_ProblemsNinetyNine Haskell Problems]], based on [https://sites.google.com/site/prologsite/prologproblems NinetyNine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L99_NinetyNine_Lisp_Problems.html NinetyNine 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 == 
== Problem 1 == 

−  (*) Find the last box of a list. 
+  (*) Find the last element of a list. 
−  Example: 
+  (Note that the Lisp transcription of this problem is incorrect.) 
−  
−  <pre> 

−  * (mylast '(a b c d)) 

−  (D) 

−  </pre> 

Example in Haskell: 
Example in Haskell: 

<haskell> 
<haskell> 

−  Prelude> last [1,2,3,4] 
+  Prelude> myLast [1,2,3,4] 
4 
4 

−  Prelude> last ['x','y','z'] 
+  Prelude> myLast ['x','y','z'] 
'z' 
'z' 

</haskell> 
</haskell> 

−  Solution: 
+  [[99 questions/Solutions/1  Solutions]] 
−  <haskell> 

−  last :: [a] > a 

−  last [x] = x 

−  last (_:xs) = last xs 

−  </haskell> 

−  
−  This function is defined in Prelude. 

== Problem 2 == 
== Problem 2 == 

−  (*) Find the last but one box of a list. 
+  (*) Find the last but one element of a list. 
−  <pre> 

−  Example: 

−  * (mybutlast '(a b c d)) 

−  (C D) 

−  </pre> 

−  This can be done by dropping all but the last two elements of a list: 
+  (Note that the Lisp transcription of this problem is incorrect.) 
+  
+  Example in Haskell: 

<haskell> 
<haskell> 

−  myButLast :: [a] > [a] 
+  Prelude> myButLast [1,2,3,4] 
−  myButLast list = drop ((length list)  2) list 
+  3 
+  Prelude> myButLast ['a'..'z'] 

+  'y' 

</haskell> 
</haskell> 

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

+  
== Problem 3 == 
== Problem 3 == 

−  (*) Find the K'th element of a list. 
+  (*) Find the K'th element of a list. The first element in the list is number 1. 
−  The first element in the list is number 1. 
+  
−  <pre> 

Example: 
Example: 

+  
+  <pre> 

* (elementat '(a b c d e) 3) 
* (elementat '(a b c d e) 3) 

−  C 
+  c 
</pre> 
</pre> 

−  This is (almost) the infix operator !! in Prelude, which is defined as: 
+  Example in Haskell: 
<haskell> 
<haskell> 

−  (!!) :: [a] > Int > a 
+  Prelude> elementAt [1,2,3] 2 
−  (x:_) !! 0 = x 
+  2 
−  (_:xs) !! n = xs !! (n1) 
+  Prelude> elementAt "haskell" 5 
+  'e' 

</haskell> 
</haskell> 

−  Except this doesn't quite work, because !! is zeroindexed, and elementat should be oneindexed. So: 
+  [[99 questions/Solutions/3  Solutions]] 
−  <haskell> 

−  elementAt :: [a] > Int > a 

−  elementAt list i = list !! (i1) 

−  </haskell> 

== Problem 4 == 
== Problem 4 == 

Line 67:  Line 61:  
(*) Find the number of elements of a list. 
(*) Find the number of elements of a list. 

−  This is "length" in Prelude, which is defined as: 
+  Example in Haskell: 
<haskell> 
<haskell> 

−  length :: [a] > Int 
+  Prelude> myLength [123, 456, 789] 
−  length [] = 0 
+  3 
−  length (_:l) = 1 + length l 
+  Prelude> myLength "Hello, world!" 
+  13 

</haskell> 
</haskell> 

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

+  
== Problem 5 == 
== Problem 5 == 

Line 79:  Line 76:  
(*) Reverse a list. 
(*) Reverse a list. 

−  This is "reverse" in Prelude, which is defined as: 
+  Example in Haskell: 
<haskell> 
<haskell> 

−  reverse :: [a] > [a] 
+  Prelude> reverse "A man, a plan, a canal, panama!" 
−  reverse = foldl (flip (:)) [] 
+  "!amanap ,lanac a ,nalp a ,nam A" 
+  Prelude> reverse [1,2,3,4] 

+  [4,3,2,1] 

</haskell> 
</haskell> 

−  The standard definition is concise, but not very readable. Another way to define reverse is: 
+  [[99 questions/Solutions/5  Solutions]] 
−  <haskell> 

−  reverse :: [a] > [a] 

−  reverse [] = [] 

−  reverse (x:xs) = reverse xs ++ [x] 

−  </haskell> 

== Problem 6 == 
== Problem 6 == 

Line 98:  Line 90:  
(*) Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x). 
(*) 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: 
+  Example in Haskell: 
<haskell> 
<haskell> 

−  isPalindrome :: (Eq a) => [a] > Bool 
+  *Main> isPalindrome [1,2,3] 
−  isPalindrome xs = xs == (reverse xs) 
+  False 
+  *Main> isPalindrome "madamimadam" 

+  True 

+  *Main> isPalindrome [1,2,4,8,16,8,4,2,1] 

+  True 

</haskell> 
</haskell> 

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

+  
== Problem 7 == 
== Problem 7 == 

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

−  <pre> 

Example: 
Example: 

+  
+  <pre> 

* (myflatten '(a (b (c d) e))) 
* (myflatten '(a (b (c d) e))) 

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

</pre> 
</pre> 

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

−  may not) be nested: 

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

<haskell> 
<haskell> 

−  data NestedList a = Elem a  List [NestedList a] 
+  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) 

</haskell> 
</haskell> 

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

−  
−  <pre> 

*Main> flatten (Elem 5) 
*Main> flatten (Elem 5) 

[5] 
[5] 

Line 130:  Line 127:  
*Main> flatten (List []) 
*Main> flatten (List []) 

[] 
[] 

−  </pre> 
+  </haskell> 
+  
+  
+  
+  [[99 questions/Solutions/7  Solutions]] 

== Problem 8 == 
== Problem 8 == 

Line 138:  Line 135:  
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. 

−  <pre> 

Example: 
Example: 

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

−  *Main> compress ['a','a','a','a','b','c','c','a','a','d','e','e','e','e'] 

−  ['a','b','c','a','d','e'] 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  compress :: Eq a => [a] > [a] 
+  > compress ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"] 
−  compress = map head . group 
+  ["a","b","c","a","d","e"] 
</haskell> 
</haskell> 

−  We simply group equal values together (group), then take the head of each. 
+  [[99 questions/Solutions/8  Solutions]] 
−  Note that (with GHC) we must give an explicit type to ''compress'' otherwise we get: 

−  
−  <haskell> 

−  Ambiguous type variable `a' in the constraint: 

−  `Eq a' 

−  arising from use of `group' 

−  Possible cause: the monomorphism restriction applied to the following: 

−  compress :: [a] > [a] 

−  Probable fix: give these definition(s) an explicit type signature 

−  or use fnomonomorphismrestriction 

−  </haskell> 

−  
−  We can circumvent the monomorphism restriction by writing ''compress'' this way (See: section 4.5.4 of [http://haskell.org/onlinereport the report]): 

−  
−  <haskell>compress xs = map head $ group xs</haskell> 

== Problem 9 == 
== Problem 9 == 

Line 161:  Line 156:  
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> 

−  Example: 

* (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)) 

−  <example in lisp> 
+  </pre> 
Example in Haskell: 
Example in Haskell: 

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  group (x:xs) = let (first,rest) = span (==x) xs 
+  *Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 
−  in (x:first) : group rest 
+  'a', 'd', 'e', 'e', 'e', 'e'] 
−  group [] = [] 
+  ["aaaa","b","cc","aa","d","eeee"] 
</haskell> 
</haskell> 

−  'group' is also in the Prelude, here's an implementation using 'span'. 
+  [[99 questions/Solutions/9  Solutions]] 
−  +  
== Problem 10 == 
== Problem 10 == 

Line 188:  Line 180:  
Example: 
Example: 

<pre> 
<pre> 

−  * (encode '(a a a a b c c a a d e e e e)) 
+  * (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> 
+  ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E)) 
−  +  </pre> 

−  Example: 

−  <example in lisp> 

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> 

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

−  </pre> 

−  Solution: 

−  <haskell> 

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

−  </haskell> 

−  
[[Category:Tutorials]] 
[[Category:Tutorials]] 
Revision as of 16:10, 5 October 2012
This is part of NinetyNine Haskell Problems, based on NinetyNine Prolog Problems and NinetyNine Lisp Problems.
1 Problem 1
(*) Find the last element of a list.
(Note that the Lisp transcription of this problem is incorrect.)
Example in Haskell:
Prelude> myLast [1,2,3,4] 4 Prelude> myLast ['x','y','z'] 'z'
2 Problem 2
(*) Find the last but one element of a list.
(Note that the Lisp transcription of this problem is incorrect.)
Example in Haskell:
Prelude> myButLast [1,2,3,4] 3 Prelude> myButLast ['a'..'z'] 'y'
3 Problem 3
(*) Find the K'th element of a list. The first element in the list is number 1.
Example:
* (elementat '(a b c d e) 3) c
Example in Haskell:
Prelude> elementAt [1,2,3] 2 2 Prelude> elementAt "haskell" 5 'e'
4 Problem 4
(*) Find the number of elements of a list.
Example in Haskell:
Prelude> myLength [123, 456, 789] 3 Prelude> myLength "Hello, world!" 13
5 Problem 5
(*) Reverse a list.
Example in Haskell:
Prelude> reverse "A man, a plan, a canal, panama!" "!amanap ,lanac a ,nalp a ,nam A" Prelude> reverse [1,2,3,4] [4,3,2,1]
6 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:
*Main> isPalindrome [1,2,3] False *Main> isPalindrome "madamimadam" True *Main> isPalindrome [1,2,4,8,16,8,4,2,1] True
7 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:
* (myflatten '(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]
*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 []) []
8 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 ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"] ["a","b","c","a","d","e"]
9 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:
*Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'] ["aaaa","b","cc","aa","d","eeee"]
10 Problem 10
(*) Runlength encoding of a list. Use the result of problem P09 to implement the socalled runlength 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')]