Difference between revisions of "99 questions/1 to 10"
m (Fixed definition of equivalent definition using concatMap for the Elem case) 
m (→Problem 8) 

(50 intermediate revisions by 27 users not shown)  
Line 1:  Line 1:  
__NOTOC__ 
__NOTOC__ 

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

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

4 
4 

−  +  λ> 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 
+  (*) 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 
+  λ> myButLast [1,2,3,4] 
−  +  3 

+  λ> 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. 
−  +  
−  <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 

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

−  (x:_) !! 0 = x 

+  2 

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

+  λ> 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 72:  Line 64:  
(*) 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 

+  λ> myLength [123, 456, 789] 

−  length [] = 0 

+  3 

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

+  λ> myLength "Hello, world!" 

+  13 

</haskell> 
</haskell> 

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

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

Line 84:  Line 80:  
(*) Reverse a list. 
(*) Reverse a list. 

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

+  Example in Haskell: 

<haskell> 
<haskell> 

−  reverse :: [a] > [a] 

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

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

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

+  λ> myReverse [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 103:  Line 96:  
(*) 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 
+  λ> isPalindrome [1,2,3] 
−  +  False 

+  λ> isPalindrome "madamimadam" 

+  True 

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

+  True 

</haskell> 
</haskell> 

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

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

Line 115:  Line 111:  
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). 

+  
+  Example: 

<pre> 
<pre> 

−  Example: 

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

+  λ> flatten (Elem 5) 

−  
−  <pre> 

−  *Main> 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 []) 

[] 
[] 

−  </pre> 

−  
−  An equivalent definition for flatten is 

−  <haskell> 

−  flatten (Elem x) = [x] 

−  flatten (List x) = concatMap flatten x 

</haskell> 
</haskell> 

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

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

Line 154:  Line 145:  
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 "aaaabccaadeeee" 

−  compress = map head . group 

+  "abcade" 

</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 192:  Line 166:  
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 

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

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

−  +  ["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 219:  Line 190:  
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: 

−  <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]] 
Latest revision as of 09:06, 9 February 2019
This is part of NinetyNine Haskell Problems, based on NinetyNine Prolog Problems and NinetyNine 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:
* (elementat '(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:
* (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]
λ> 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
(*) 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')]