Difference between revisions of "99 questions/1 to 10"
(Moved solutions to first 5 problems to new subpages of 99 problems/Solutions) 
m (→Problem 8) 

(13 intermediate revisions by 9 users not shown)  
Line 1:  Line 1:  
__NOTOC__ 
__NOTOC__ 

−  This is part of [[H99:_NinetyNine_Haskell_ProblemsNinetyNine Haskell Problems]], based on [https:// 
+  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 == 

Line 12:  Line 12:  
<haskell> 
<haskell> 

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

4 
4 

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

'z' 
'z' 

</haskell> 
</haskell> 

Line 30:  Line 30:  
<haskell> 
<haskell> 

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

3 
3 

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

'y' 
'y' 

</haskell> 
</haskell> 

−  [[99 
+  [[99 questions/Solutions/2  Solutions]] 
Line 47:  Line 47:  
<pre> 
<pre> 

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

−  C 

+  c 

</pre> 
</pre> 

Line 53:  Line 53:  
<haskell> 
<haskell> 

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

2 
2 

−  +  λ> elementAt "haskell" 5 

'e' 
'e' 

</haskell> 
</haskell> 

−  [[99 
+  [[99 questions/Solutions/3  Solutions]] 
Line 69:  Line 69:  
<haskell> 
<haskell> 

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

3 
3 

−  +  λ> myLength "Hello, world!" 

13 
13 

</haskell> 
</haskell> 

−  [[99 
+  [[99 questions/Solutions/4  Solutions]] 
Line 85:  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 
+  [[99 questions/Solutions/5  Solutions]] 
Line 101:  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> 

−  Solution: 

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

−  <haskell> 

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

−  isPalindrome xs = xs == (reverse xs) 

−  </haskell> 

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

Line 131:  Line 127:  
Example in Haskell: 
Example in Haskell: 

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

<haskell> 
<haskell> 

−  *Main> flatten (Elem 5) 

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

−  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 define 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 163:  Line 151:  
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> 

−  
−  An alternative solution is 

−  
−  <haskell> 

−  compress [] = [] 

−  compress [a] = [a] 

−  compress (x : y : xs) = (if x == y then [] else [x]) ++ compress (y : xs) 

−  </haskell> 

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

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

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

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

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

−  </pre> 

−  Solution: 

<haskell> 
<haskell> 

−  pack (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> 

−  A more verbose solution is 

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

−  <haskell> 

−  pack :: Eq a => [a] > [[a]] 

−  pack [] = [] 

−  pack (x:xs) = (x:first) : pack rest 

−  where 

−  getReps [] = ([], []) 

−  getReps (y:ys) 

−   y == x = let (f,r) = getReps ys in (y:f, r) 

−   otherwise = ([], (y:ys)) 

−  (first,rest) = getReps xs 

−  </haskell> 

−  
−  This is implemented as <hask>group</hask> in <hask>Data.List</hask>. 

== Problem 10 == 
== Problem 10 == 

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

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

−  which can also be expressed as a list comprehension: 

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

−  <haskell> 

−  [(length x, head x)  x < group xs] 

−  </haskell> 

−  Or writing it [[Pointfree]]: 

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