99 Haskell Problems

A Haskell beginner tutorial by solving simple problems.

Problem 25

99 Haskell Problems

Problem 25

Generate a random permutation of the elements of a list.

Example:

* (rnd-permu '(a b c d e f))
(B A D C E F)

Example in Haskell:

Prelude System.Random>rnd_permu "abcdef"
Prelude System.Random>"badcef"

Solution:

Using the nub solution from Problem 23 again,

rnd_permu xs = rnd_select xs (length xs)

With rnd_select as:

rnd_select :: [a] -> Int -> [a]
rnd_select x n = map (x!!) is
 where is = take n . nub $ randomRs (0, length x - 1) (mkStdGen 100)

Additional References:

Advertisements

Problem 24

99 Haskell Problems

Problem 24

Lotto: Draw N different random numbers from the set 1..M.

Example:

* (rnd-select 6 49)
(23 1 17 33 21 37)

Example in Haskell:

Prelude System.Random>diff_select 6 49
Prelude System.Random>[23,1,17,33,21,37]

Solution:

Using the nub solution from Problem 23 to remove any duplicates, this become very easy.

diff_select n m = rnd_select [1..m] n

With rnd_select as:

rnd_select :: [a] -> Int -> [a]
rnd_select x n = map (x!!) is
 where is = take n . nub $ randomRs (0, length x - 1) (mkStdGen 100)

Additional References:

Problem 23

99 Haskell Problems

Problem 23

Extract a given number of randomly selected elements from a list.

Example:

* (rnd-select '(a b c d e f g h) 3)
(E D A)

Example in Haskell:

Prelude System.Random>rnd_select "abcdefgh" 3 >>= putStrLn
eda

Solution:

Random number seems to be a departure from what I have learn about functional language as it is suppose to be referential transparent. Since I have not deal with random number in Haskell, some reading was needed. In particular, I learn a new notation call do block that helps initialize my random generator g.

rnd_select xs n = do
 g <- newStdGen
 print $ rndS xs n g

rndS [] _ _ = []
rndS xs n g
 | n == 0 = []
 | otherwise = (xs !! r) : rndS xs (n-1) gen
 where (r, gen) = randomR (0, ((length xs) - 1)) g

Using randomR in rndS function, I can pick a number from 0 upto length of the list minus 1 and use that number to pick the element. The most interesting part are the type for rndS and rnd_select:

rnd_select :: (Eq a1, Num a1, Show a) => [a] -> a1 -> IO ()
rndS :: (Eq a1, Num a1, RandomGen t) => [a] -> a1 -> t -> [a]

rndS is expected. However, rnd_select using do block, the output become IO() instead of [a]. A more elegant result from the solution is to use list comprehension:

rnd_select xs n = do
 g <- newStdGen
 return $ take n [ xs !! x | x <- randomRs (0, (length xs) - 1) g]

However, this still using IO[a] instead of [a] as the result. The solution was to use nub in yet another result from the solution section but now if you run the function in consecutive times, the result will be the same.

rnd_select :: [a] -> Int -> [a]
rnd_select x n = map (x!!) is
 where is = take n . nub $ randomRs (0, length x - 1) (mkStdGen 100)

Additional References:

Problem 22

99 Haskell Problems

Problem 22

Create a list containing all integers within a given range.

Example:

* (range 4 9)
(4 5 6 7 8 9)

Example in Haskell:

Prelude> range 4 9
[4,5,6,7,8,9]

Solution:

range :: Int -> Int -> [Int]
range start end
    | start > end = []
    | start == end = [end]
    | otherwise = start:(range (start+1) end)

Avoid exception by having a check return empty list if start is greater than end. However, the language provided range function as

range start end = [start..end]

Problem 21

99 Haskell Problems

Problem 21

Insert an element at a given position into a list.

Example:

* (insert-at 'alfa '(a b c d) 2)
(A ALFA B C D)

Example in Haskell:

P21> insertAt 'X' "abcd" 2
"aXbcd"

Solution:

insertAt :: a -> [a] -> Int -> [a]
insertAt x [] _ = [x]
insertAt x (y:ys) n
 | n > length(y:ys) = (y:ys) ++ [x]
 | n <= 1 = x:(y:ys)
 | otherwise = y:(insertAt x ys (n-1))

Any n less than or equal to 1 will assume the element will insert at the head and any n greater than the length of the list will be at the tail.

Problem 20

99 Haskell Problems

Problem 20

(*) Remove the K’th element from a list.

Example in Prolog:

?- remove_at(X,[a,b,c,d],2,R).
X = b
R = [a,c,d]

Example in Lisp:

* (remove-at '(a b c d) 2)
(A C D)

(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)

Example in Haskell:

*Main> removeAt 2 "abcd"
('b',"acd")

Solution:

removeAt :: Int -> [a] -> (a, [a])
removeAt n (x:xs) 
    | n == 1 = (x, xs)
    | otherwise = (ys, x:zs)
        where (ys, zs) = removeAt (n-1) xs

This is similar to the solution from problem 17. we use the where clause to connect the missing link between ys, zs and xs.

Problem 19

99 Haskell Problems

Problem 19

(**) Rotate a list N places to the left.

Hint: Use the predefined functions length and (++).

Examples:

* (rotate '(a b c d e f g h) 3)
(D E F G H A B C)

* (rotate '(a b c d e f g h) -2)
(G H A B C D E F)

Examples in Haskell:

*Main> rotate ['a','b','c','d','e','f','g','h'] 3
"defghabc"
 
*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)
"ghabcdef"

Solution:

rotate :: [a] -> Int -> [a]
rotate [] _ = []
rotate xs 0 = xs
rotate (x:xs) n 
 | n > 0 = rotate (xs++[x]) (n-1)
 | otherwise = rotate (x:xs) (length (x:xs) + n)

The case n < 0 is represented in the otherwise by call rotate with a positive value.