Difference between revisions of "99 questions/1 to 10"

From HaskellWiki
Jump to: navigation, search
(Added a non-reconsing variation for P5)
m (Problem 8)
 
(31 intermediate revisions by 18 users not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
   
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems].
+
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://sites.google.com/site/prologsite/prolog-problems Ninety-Nine Prolog Problems] and [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine 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>
 
* (my-last '(a b c d))
 
(D)
 
</pre>
 
   
 
Example in Haskell:
 
Example in Haskell:
   
 
<haskell>
 
<haskell>
Prelude> myLast [1,2,3,4]
+
λ> myLast [1,2,3,4]
[4]
+
4
Prelude> myLast ['x','y','z']
+
λ> 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>
 
* (my-but-last '(a b c d))
 
(C D)
 
</pre>
 
   
 
Example in Haskell:
 
Example in Haskell:
   
 
<haskell>
 
<haskell>
Prelude> myButLast [1,2,3,4]
+
λ> myButLast [1,2,3,4]
[3,4]
+
3
Prelude> myButLast ['a'..'z']
+
λ> 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 list = snd $ splitAt (length list - 2) list
 
</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 98: Line 47:
 
<pre>
 
<pre>
 
* (element-at '(a b c d e) 3)
 
* (element-at '(a b c d e) 3)
C
 
  +
c
 
</pre>
 
</pre>
   
Line 104: Line 53:
   
 
<haskell>
 
<haskell>
Prelude> elementAt [1,2,3] 2
+
λ> elementAt [1,2,3] 2
 
2
 
2
Prelude> elementAt "haskell" 5
+
λ> 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 !! (n-1)
 
</haskell>
 
 
Except this doesn't quite work, because !! is zero-indexed, and element-at should be one-indexed. So:
 
 
<haskell>
 
elementAt :: [a] -> Int -> a
 
elementAt list i = list !! (i-1)
 
</haskell>
 
   
 
== Problem 4 ==
 
== Problem 4 ==
Line 134: Line 69:
   
 
<haskell>
 
<haskell>
Prelude> length [123, 456, 789]
+
λ> myLength [123, 456, 789]
 
3
 
3
Prelude> length "Hello, world!"
+
λ> 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 157: Line 85:
   
 
<haskell>
 
<haskell>
Prelude> reverse "A man, a plan, a canal, panama!"
+
λ> myReverse "A man, a plan, a canal, panama!"
 
"!amanap ,lanac a ,nalp a ,nam A"
 
"!amanap ,lanac a ,nalp a ,nam A"
Prelude> reverse [1,2,3,4]
+
λ> 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>
 
 
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 ==
Line 195: Line 101:
   
 
<haskell>
 
<haskell>
*Main> isPalindrome [1,2,3]
+
λ> isPalindrome [1,2,3]
 
False
 
False
*Main> isPalindrome "madamimadam"
+
λ> isPalindrome "madamimadam"
 
True
 
True
*Main> isPalindrome [1,2,4,8,16,8,4,2,1]
+
λ> 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 224: 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>
*Main> flatten (Elem 5)
+
λ> flatten (Elem 5)
 
[5]
 
[5]
*Main> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 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]
*Main> flatten (List [])
+
λ> 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 256: 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 -fno-monomorphism-restriction
 
</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 312: 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',
in (x:first) : pack rest
+
'a', 'd', 'e', 'e', 'e', 'e']
pack [] = []
+
["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 340: 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>
   
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 Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems and Ninety-Nine 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'

Solutions


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'

Solutions


Problem 3

(*) Find the K'th element of a list. The first element in the list is number 1.

Example:

* (element-at '(a b c d e) 3)
c

Example in Haskell:

λ> elementAt [1,2,3] 2
2
λ> elementAt "haskell" 5
'e'

Solutions


Problem 4

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

Example in Haskell:

λ> myLength [123, 456, 789]
3
λ> myLength "Hello, world!"
13

Solutions


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]

Solutions


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

Solutions


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:

* (my-flatten '(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 [])
[]


Solutions

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"

Solutions

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

Solutions

Problem 10

(*) Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length 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')]

Solutions