Difference between revisions of "99 questions/1 to 10"
RossPaterson (talk  contribs) m (new URL) 
m (→Problem 8) 

(33 intermediate revisions by 19 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 == 

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

−  +  λ> myLast ['x','y','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 
+  (*) 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: 

<haskell> 
<haskell> 

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

−  +  3 

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

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

−  or 

−  <haskell> 

−  myButLast [a, b] = [a, b] 

−  myButLast (_ : xs) = myButLast xs 

−  </haskell> 

−  (I'm very new to Haskell but this last one definitely seems to work  bakert.) 

−  
−  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 94:  Line 47:  
<pre> 
<pre> 

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

−  C 

+  c 

</pre> 
</pre> 

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

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

2 
2 

−  +  λ> elementAt "haskell" 5 

'e' 
'e' 

</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 130:  Line 69:  
<haskell> 
<haskell> 

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

3 
3 

−  +  λ> 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 153:  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> 

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

−  +  λ> 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 242:  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 "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> 

−  
−  Another alternative is to use the Data.Set module to construct a Set. This solution also works if the repeated elements are not consecutive. This solution is potentially incorrect in the spirit of this quiz as it creates a data structure of a new type (Set), but still addresses the problem in question. 

−  
−  <pre> 

−  Prelude> let r = ["a","a","b","b","c","c","c"] 

−  Prelude> :m Data.Set 

−  Prelude Data.Set> let s = fromList r 

−  Prelude Data.Set> s 

−  fromList ["a","b","c"] 

−  </pre> 

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

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

−  'group' is also in the Prelude, here's an implementation using 'span'. 

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

−  
+  
== Problem 10 == 
== Problem 10 == 

Line 326:  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')]