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

From HaskellWiki
Jump to: navigation, search
(Added 3 & 4 from prelude, and a trivial definition of 5)
(all haskell solutions have been added)
 
(78 intermediate revisions by 20 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://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ 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://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ P-99: Ninety-Nine Prolog Problems] 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.
 
  +
* [http://www.oreillynet.com/onlamp/blog/2006/12/99_problems_in_perl_6.html 99 Problems in Perl 6] has an increasing number of Perl 6 solutions (running on [http://www.pugscode.org/ Pugs]).
Example:
 
  +
* [http://www.christiankissig.de/cms/index.php/en/programming/28-ocaml/28-99-problems-in-ocaml 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>
 
 
== 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>
 
   
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]
  +
[[Category:Code]]

Latest revision as of 20:39, 22 November 2013


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