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

(34 intermediate revisions by 16 users not shown)  
Line 1:  Line 1:  
__NOTOC__ 
__NOTOC__ 

−  This is part of [[H99:_NinetyNine_Haskell_ProblemsNinetyNine Haskell Problems]], based on [http://www.htabi.bfh.ch/~hew/informatik3/prolog/p99/ NinetyNine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L99_NinetyNine_Lisp_Problems.html NinetyNine 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: 

Line 13:  Line 13:  
<haskell> 
<haskell> 

Prelude> myLast [1,2,3,4] 
Prelude> myLast [1,2,3,4] 

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

−  "z" 
+  'z' 
</haskell> 
</haskell> 

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

−  myLast :: [a] > [a] 

−  myLast [x] = [x] 

−  myLast (_:xs) = myLast xs 

−  </haskell> 

−  
−  Haskell also provides the function <hask>last</hask>. 

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

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

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

−  (C D) 

−  </pre> 

Example in Haskell: 
Example in Haskell: 

Line 38:  Line 31:  
<haskell> 
<haskell> 

Prelude> myButLast [1,2,3,4] 
Prelude> myButLast [1,2,3,4] 

−  [3,4] 
+  3 
Prelude> myButLast ['a'..'z'] 
Prelude> myButLast ['a'..'z'] 

−  "yz" 
+  'y' 
</haskell> 
</haskell> 

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

−  myButLast :: [a] > [a] 

−  myButLast list = drop ((length list)  2) list 

−  </haskell> 

−  
−  This simply drops all the but last two elements of a list. 

−  
−  Some other options: 

−  <haskell> 

−  myButLast = reverse . take 2 . reverse 

−  </haskell> 

−  or 

−  <haskell> 

−  myButLast = last . liftM2 (zipWith const) tails (drop 1) 

−  </haskell> 

−  
−  Remark: 

−  The Lisp solution is actually wrong, it should not be the last two elements; a correct Haskell solution is: 

−  <haskell> 

−  myButLast = last . init 

−  Prelude> myButLast ['a'..'z'] 

−  'y' 

−  </haskell> 

−  See also the solution to problem 2 in the Prolog list. 

== Problem 3 == 
== Problem 3 == 

Line 78:  Line 47:  
<pre> 
<pre> 

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

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

Line 90:  Line 59:  
</haskell> 
</haskell> 

−  Solution: 
+  [[99 questions/Solutions/3  Solutions]] 
−  This is (almost) the infix operator !! in Prelude, which is defined as: 

−  
−  <haskell> 

−  (!!) :: [a] > Int > a 

−  (x:_) !! 0 = x 

−  (_:xs) !! n = xs !! (n1) 

−  </haskell> 

−  
−  Except this doesn't quite work, because !! is zeroindexed, and elementat should be oneindexed. So: 

−  
−  <haskell> 

−  elementAt :: [a] > Int > a 

−  elementAt list i = list !! (i1) 

−  </haskell> 

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

Line 114:  Line 69:  
<haskell> 
<haskell> 

−  Prelude> length [123, 456, 789] 
+  Prelude> myLength [123, 456, 789] 
3 
3 

−  Prelude> length "Hello, world!" 
+  Prelude> myLength "Hello, world!" 
13 
13 

</haskell> 
</haskell> 

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

−  length :: [a] > Int 

−  length [] = 0 

−  length (_:l) = 1 + length l 

−  </haskell> 

−  This function is defined in Prelude. 

== Problem 5 == 
== Problem 5 == 

Line 137:  Line 91:  
</haskell> 
</haskell> 

−  Solution: (defined in Prelude) 
+  [[99 questions/Solutions/5  Solutions]] 
−  <haskell> 

−  reverse :: [a] > [a] 

−  reverse = foldl (flip (:)) [] 

−  </haskell> 

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

−  
−  <haskell> 

−  reverse :: [a] > [a] 

−  reverse [] = [] 

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

−  </haskell> 

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

Line 167:  Line 109:  
</haskell> 
</haskell> 

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

−  isPalindrome :: (Eq a) => [a] > Bool 

−  isPalindrome xs = xs == (reverse xs) 

−  </haskell> 

== Problem 7 == 
== Problem 7 == 

Line 188:  Line 126:  
Example in Haskell: 
Example in Haskell: 

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

+  <haskell> 

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

+  </haskell> 

<haskell> 
<haskell> 

Line 198:  Line 141:  
</haskell> 
</haskell> 

−  Solution: 

−  <haskell> 

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

−  flatten :: NestedList a > [a] 
+  [[99 questions/Solutions/7  Solutions]] 
−  flatten (Elem x) = [x] 

−  flatten (List x) = concatMap flatten x 

−  </haskell> 

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

−  [1, [2, [3, 4], 5]] is a type error. Therefore, we must have a way of 

−  representing a list that may (or may not) be nested. 

−  
−  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]). 

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

Line 210:  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> 

−  Example: 

* (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 234:  Line 172:  
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 261:  Line 196:  
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)) 
+  ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E)) 
</pre> 
</pre> 

Example in Haskell: 
Example in Haskell: 

−  <pre> 
+  <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')] 

−  </pre> 

−  
−  Solution: 

−  <haskell> 

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

</haskell> 
</haskell> 

−  Or writing it [[Pointfree]]: 
+  [[99 questions/Solutions/10  Solutions]] 
−  <haskell> 

−  encode :: Eq a => [a] > [(Int, a)] 

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

−  </haskell> 

−  Or (ab)using the "&&&" arrow operator for tuples: 

−  
−  <haskell> 

−  encode :: Eq a => [a] > [(Int, a)] 

−  encode xs = map (length &&& head) $ 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')]