H-99: Ninety-Nine Haskell Problems: Difference between revisions

From HaskellWiki
No edit summary
m (fixed link for ocaml's exercise list)
 
(76 intermediate revisions by 23 users not shown)
Line 1: Line 1:
These are Haskell translations of [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety Nine Lisp Problems].
__NOTOC__


== Problem 1 ==
These are Haskell translations of [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety-Nine Lisp Problems],
which are themselves translations of [https://web.archive.org/web/20170324220754/https://sites.google.com/site/prologsite/prolog-problems Ninety-Nine Prolog Problems].


<pre>
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 Haskell>,<solution in haskell> and <description of implementation> fields. Then be sure to update the status on this page to indicate that we have a solution!
(*) Find the last box of a list.
Example:
* (my-last '(a b c d))
(D)
</pre>


This is "last" in Prelude, which is defined as:
== The problems ==


<haskell>
These problems have been split into 11 parts, for ease of access.
last :: [a] -> a
last [x] = x
last (_:xs) = last xs
</haskell>


== Problem 2 ==
* [[99_questions/1_to_10|Questions 1 to 10]]: Lists
* [[99_questions/11_to_20|Questions 11 to 20]]: Lists, continued
* [[99_questions/21_to_28|Questions 21 to 28]]: Lists again
* [[99_questions/31_to_41|Questions 31 to 41]]: Arithmetic
* [[99_questions/46_to_50|Questions 46 to 50]]: Logic and codes
* [[99_questions/54A_to_60|Questions 54A to 60]]: Binary trees
* [[99_questions/61_to_69|Questions 61 to 69]]: Binary trees, continued
* [[99_questions/70B_to_73|Questions 70B to 73]]: Multiway trees
* [[99_questions/80_to_89|Questions 80 to 89]]: Graphs
* [[99_questions/90_to_94|Questions 90 to 94]]: Miscellaneous problems
* [[99_questions/95_to_99|Questions 95 to 99]]: Miscellaneous problems, continued


<pre>
(Though the problems number from 1 to 99, there are some gaps and some additions marked with letters. There are actually only 88 problems.)
(*) Find the last but one box of a list.
Example:
* (my-but-last '(a b c d))
(C D)
</pre>


This can be done by dropping all but the last two elements of a list:
== Solutions ==


<haskell>
Known solutions are listed at [[99 questions/Solutions]]. Some of those we have could do with cleaning up or additional solutions.
myButLast :: [a] -> [a]
myButLast list = drop ((length list) - 2) list
</haskell>


== Problem 3 ==
== References ==


<pre>
* [https://web.archive.org/web/20170324220754/https://sites.google.com/site/prologsite/prolog-problems P-99: Ninety-Nine Prolog Problems] (Wayback Machine; original link now dead) contains Prolog solutions to all the problems.
(*) Find the K'th element of a list.
* [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html L-99: Ninety-Nine Lisp Problems] contains Lisp solutions to problems 1-11, 14, 15, 17 and 20-28.
The first element in the list is number 1.
* [https://www.perlmonks.org/?node_id=590113 99 Problems in Perl 6] has an increasing number of Perl 6 solutions.
Example:
* [https://www.ocaml.org/exercises 99 Problems in OCaml] contains Ocaml solutions to many problems.
* (element-at '(a b c d e) 3)
C
</pre>


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 ==
<pre>
(*) Find the number of elements of a list.
</pre>
This is "length" in Prelude, which is defined as:
<haskell>
length          :: [a] -> Int
length []        =  0
length (_:l)    =  1 + length l
</haskell>
== Problem 5 ==
<pre>
(*) Reverse a list.
</pre>
This is "reverse" in Prelude, which is defined as:
<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 ==
<pre>
(*) Find out whether a list is a palindrome.
A palindrome can be read forward or backward; e.g. (x a m a x).
</pre>
This is trivial, because we can use reverse:
<haskell>
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == (reverse xs)
</haskell>
== Problem 7 ==
<pre>
(**) 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)
</pre>
This is tricky, because lists in Haskell are homogeneous. [1, [2, [3, 4], 5]]
is a type error. We have to devise some way of represent a list that may (or
may not) be nested:
<haskell>
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>
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]). Let's try it out in ghci:
<pre>
*Main> flatten (Elem 5)
[5]
*Main> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
[1,2,3,4,5]
*Main> flatten (List [])
[]
</pre>
== Problem 8 ==
<pre>
(**) 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:
*Main> compress ['a','a','a','a','b','c','c','a','a','d','e','e','e','e']
['a','b','c','a','d','e']
</pre>
<haskell>
compress = map head . group
</haskell>
We simply group equal values together (group), then take the head of each.
       
[[Category:Tutorials]]
[[Category:Tutorials]]
[[Category:Code]]

Latest revision as of 19:49, 4 January 2024


These are Haskell translations of Ninety-Nine Lisp Problems, which are themselves translations of Ninety-Nine Prolog 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 Haskell>,<solution in haskell> and <description of implementation> fields. Then be sure to update the status on this page to indicate that we have a solution!

The problems

These problems have been split into 11 parts, for ease of access.

(Though the problems number from 1 to 99, there are some gaps and some additions marked with letters. There are actually only 88 problems.)

Solutions

Known solutions are listed at 99 questions/Solutions. Some of those we have could do with cleaning up or additional solutions.

References

Retrieved from "https://wiki.haskell.org/index.php?title=H-99:_Ninety-Nine_Haskell_Problems&oldid=66483"