Difference between revisions of "99 questions/1 to 10"
RossPaterson (talk  contribs) m (whitespace only) 
m 

(26 intermediate revisions by 15 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 == 

+  <div style="borderbottom:1px solid #eee">(*) Find the last element of a list. <span style="float:right"><small>[[99 questions/Solutions/1Solutions]]</small></span> 

+  </div> 

+  <br> 

−  ( 
+  (Note that the Lisp transcription of this problem is incorrect.) 
−  
−  (Note the the Lisp transcription of this problem is incorrect.) 

Example in Haskell: 
Example in Haskell: 

<haskell> 
<haskell> 

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

4 
4 

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

'z' 
'z' 

</haskell> 
</haskell> 

−  Solutions: 

−  
−  <haskell> 

−  myLast :: [a] > a 

−  myLast [x] = x 

−  myLast (_:xs) = myLast xs 

−  </haskell> 

−  
−  <haskell> 

−  myLast :: [a] > a 

−  myLast = foldr1 (const id) 

−  </haskell> 

−  
−  The <hask>Prelude</hask> also provides the function <hask>last</hask>. 

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

+  <div style="borderbottom:1px solid #eee">(*) Find the lastbutone (or secondlast) element of a list. <span style="float:right"><small>[[99 questions/Solutions/2Solutions]]</small></span> 

+  </div> 

+  <br> 

−  ( 
+  (Note that the Lisp transcription of this problem is incorrect.) 
−  
−  (Note the the Lisp transcription of this problem is incorrect.) 

Example in Haskell: 
Example in Haskell: 

<haskell> 
<haskell> 

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

3 
3 

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

'y' 
'y' 

</haskell> 
</haskell> 

−  Solutions: 

−  
−  <haskell> 

−  myButLast :: [a] > a 

−  myButLast = last . init 

−  </haskell> 

−  
−  <haskell> 

−  myButLast :: [a] > a 

−  myButLast [x,_] = x 

−  myButLast (_:xs) = myButLast xs 

−  </haskell> 

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

+  <div style="borderbottom:1px solid #eee">(*) Find the K'th element of a list. <span style="float:right"><small>[[99 questions/Solutions/3Solutions]]</small></span> 

+  </div> 

+  <br> 

−  +  The first element in the list is number 1. 

−  
Example: 
Example: 

<pre> 
<pre> 

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

+  c 

−  C 

</pre> 
</pre> 

Line 77:  Line 54:  
<haskell> 
<haskell> 

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

2 
2 

−  +  λ> elementAt "haskell" 5 

'e' 
'e' 

</haskell> 
</haskell> 

−  Solution: 

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

+  <div style="borderbottom:1px solid #eee">(*) Find the number of elements in a list. <span style="float:right"><small>[[99 questions/Solutions/4Solutions]]</small></span> 

−  
+  </div> 

−  (*) Find the number of elements of a list. 

+  <br> 

Example in Haskell: 
Example in Haskell: 

<haskell> 
<haskell> 

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

3 
3 

−  +  λ> myLength "Hello, world!" 

13 
13 

</haskell> 
</haskell> 

−  Solution: 

−  
−  <haskell> 

−  myLength :: [a] > Int 

−  myLength [] = 0 

−  myLength (_:xs) = 1 + myLength xs 

−  </haskell> 

−  
−  This is <hask>length</hask> in <hask>Prelude</hask>. 

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

+  <div style="borderbottom:1px solid #eee">(*) Reverse a list. <span style="float:right"><small>[[99 questions/Solutions/5Solutions]]</small></span> 

−  
+  </div> 

−  (*) Reverse a list. 

+  <br> 

Example in Haskell: 
Example in Haskell: 

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

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

−  
−  However this definition is more wasteful than the one in Prelude as it repeatedly reconses the result as it is accumulated. The following variation avoids that, and thus computationally closer to the Prelude version. 

−  
−  <haskell> 

−  reverse :: [a] > [a] 

−  reverse list = reverse' list [] 

−  where 

−  reverse' [] reversed = reversed 

−  reverse' (x:xs) reversed = reverse' xs (x:reversed) 

−  </haskell> 

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

+  <div style="borderbottom:1px solid #eee">(*) Find out whether a list is a palindrome. <span style="float:right"><small>[[99 questions/Solutions/6Solutions]]</small></span> 

+  </div> 

+  <br> 

−  +  Hint: A palindrome can be read forward or backward; e.g. (x a m a x). 

Example in Haskell: 
Example in Haskell: 

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

−  
−  <haskell> 

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

−  isPalindrome xs = xs == (reverse xs) 

−  </haskell> 

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

+  <div style="borderbottom:1px solid #eee">(**) Flatten a nested list structure. <span style="float:right"><small>[[99 questions/Solutions/7Solutions]]</small></span> 

−  
+  </div> 

−  (**) Flatten a nested list structure. 

+  <br> 

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

Line 197:  Line 125:  
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] 

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

+  <div style="borderbottom:1px solid #eee">(**) Eliminate consecutive duplicates of list elements. <span style="float:right"><small>[[99 questions/Solutions/8Solutions]]</small></span> 

−  
+  </div> 

−  (**) Eliminate consecutive duplicates of list elements. 

+  <br> 

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 "aaaabccaadeeee" 

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

+  "abcade" 

−  compress = map head . group 

</haskell> 
</haskell> 

−  We simply group equal values together (group), then take the head of each. 

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

+  <div style="borderbottom:1px solid #eee">(**) Pack consecutive duplicates of list elements into sublists. <span style="float:right"><small>[[99 questions/Solutions/9Solutions]]</small></span> 

+  </div> 

+  <br> 

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

+  </pre> 

−  <example in lisp> 

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 
+  λ> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 
−  +  'a', 'd', 'e', 'e', 'e', 'e'] 

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

−  pack [] = [] 

</haskell> 
</haskell> 

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

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

+  <div style="borderbottom:1px solid #eee">(*) Runlength encoding of a list. <span style="float:right"><small>[[99 questions/Solutions/10Solutions]]</small></span> 

+  </div> 

+  <br> 

+  Use the result of Problem 9 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. 

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

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

−  <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 05:27, 10 June 2023
This is part of NinetyNine Haskell Problems, based on NinetyNine Prolog Problems and NinetyNine Lisp Problems.
Problem 1
(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
(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
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
Example in Haskell:
λ> myLength [123, 456, 789]
3
λ> myLength "Hello, world!"
13
Problem 5
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
Hint: 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
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
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
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
Use the result of Problem 9 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')]