Haskell: 99 questions -- 1 to 10

这个系列是对于Haskell 99题的编程训练。

本期是$1\sim 10​$,关于Lists。

使用pure的函数式语言还是爽啊~。

Problem 1

(*) Find the last element of a list.

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

Example in Haskell:

1
2
3
4
λ> myLast [1,2,3,4]
4
λ> myLast ['x','y','z']
'z'

Solutions

1
2
3
4
5
-- Problem 1
myLast :: [a] -> a
myLast [] = error "No end for empty lists!"
myLast [a] = a
myLast (a:as) = myLast as

Problem 2

(*) Find the last but one element of a list.

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

Example in Haskell:

1
2
3
4
λ> myButLast [1,2,3,4]
3
λ> myButLast ['a'..'z']
'y'

Solutions

1
2
3
4
5
6
7
8
9
10
11
-- Problem 2
myButLast :: [a] -> a
myButLast [] = error "Empty list"
myButLast [a] = error "Too few elements"
myButLast [a, b] = a
myButLast (_:as) = myButLast as

myButLast' = last . init

lastbut1safe :: Foldable f => f a -> Maybe a
lastbut1safe = fst . foldl (\(a, b) x -> (b, Just x)) (Nothing, Nothing)

这里用到了last, init,对比记忆一下head, tail, last, init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Prelude> :i head
head :: [a] -> a -- Defined in ‘GHC.List’
Prelude> head [1..10]
1
Prelude> :i tail
tail :: [a] -> [a] -- Defined in ‘GHC.List’
Prelude> tail [1..10]
[2,3,4,5,6,7,8,9,10]
Prelude> :i last
last :: [a] -> a -- Defined in ‘GHC.List’
Prelude> last [1..10]
10
Prelude> :i init
init :: [a] -> [a] -- Defined in ‘GHC.List’
Prelude> init [1..10]
[1,2,3,4,5,6,7,8,9]

Problem 3

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

Example:

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

Example in Haskell:

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

Solutions

1
2
3
4
5
6
-- Problem 3
elementAt :: [a] -> Int -> a
elementAt (a:_) 1 = a
elementAt (_:as) k = elementAt as (k - 1)

elementAt' xs n = last $ take n xs

Problem 4

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

Example in Haskell:

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

Solutions

1
2
3
4
5
6
7
8
9
10
11
12
-- Problem 4
myLength :: [a] -> Int
myLength = foldr (const (+ 1)) 0

myLength' as = myLength_acc as 0 -- tail recursion
where
myLength_acc [] acc = acc
myLength_acc (_:as) acc = myLength_acc as (acc + 1)

myLength'' = fst . last . zip [1..]

myLength''' = sum . map (const 1)

这里用到了const

1
2
3
Prelude> :i const 
const :: a -> b -> a -- Defined in ‘GHC.Base’
const a _ = a

可以看出,const a是一个常函数,无论b是什么,都是a(当然a也可以使一个函数)。

在这里,myLength = foldr (\_ -> (+1)) 0,其中\_ -> (+1)可以写成const (+1)

当然,求长度还可以使用zip [1..]sum . map (const 1)这中骚操作。

Problem 5

(*) Reverse a list.

Example in Haskell:

1
2
3
4
λ> 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

1
2
3
4
5
6
7
8
9
10
11
12
-- Problem 5
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (a:as) = myReverse as ++ [a]

myReverse' as = reverse_acc as [] -- tail recursion
where
reverse_acc [] acc = acc
reverse_acc (a:as) acc = reverse_acc as (a:acc)

myReverse'' :: [a] -> [a]
myReverse'' = foldl (flip (:) ) [] -- standard definition

这里需要说的是GHC的标准实现中reverse的实现foldl (flip (:)) [],非常漂亮。

其中flip是用于翻转函数参数:

1
2
3
Prelude> :i flip
flip :: (a -> b -> c) -> b -> a -> c -- Defined in ‘GHC.Base’
flip f b a = f a b

这里对比一下foldl, foldr

1
2
3
4
5
6
7
8
9
10
11
12
Prelude> :i foldl
class Foldable (t :: * -> *) where
...
foldl :: (b -> a -> b) -> b -> t a -> b
...
-- Defined in ‘Data.Foldable’
Prelude> :i foldr
class Foldable (t :: * -> *) where
...
foldr :: (a -> b -> b) -> b -> t a -> b
...
-- Defined in ‘Data.Foldable’

关于foldl, foldr, foldl'详细的讨论参见Foldr Foldl Fold’

这里简单说明一下:

1
2
3
4
5
6
7
8
9
10
-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

Right-fold-transformation.png

Left-fold-transformation.png

foldl相比foldr,采用了tail recursion,所以可以进行更进一步的优化得到foldl'

1
2
3
> foldl' f z []     = z
> foldl' f z (x:xs) = let z' = z `f` x
> in seq z' $ foldl' f z' xs

使用foldl'虽然避免了爆栈的风险,但是失去了“lazy”的特性。

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:

1
2
3
4
5
6
λ> isPalindrome [1,2,3]
False
λ> isPalindrome "madamimadam"
True
λ> isPalindrome [1,2,4,8,16,8,4,2,1]
True

Solutions

1
2
3
4
5
6
7
8
9
10
-- Problem 6
isPalindrome :: Eq a => [a] -> Bool
isPalindrome list = list == reverse list

isPalindrome' :: Eq a => [a] -> Bool -- only half
isPalindrome' xs = p [] xs xs
where
p half (x:xs) (_:_:ys) = p (x:half) xs ys
p half (x:xs) [_] = half == xs
p half xs [] = half == xs

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:

1
2
* (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.

1
2
3
4
5
6
7
 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

1
2
3
4
5
6
-- Problem 7
data NestedList a = Elem a | List [NestedList a]

flatten :: NestedList a -> [a]
flatten (Elem a) = [a]
flatten (List as) = concat $ map flatten as -- concatMap flatten as

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:

1
2
* (compress '(a a a a b c c a a d e e e e))
(A B C A D E)

Example in Haskell:

1
2
λ> compress "aaaabccaadeeee"
"abcade"

Solutions

1
2
3
4
5
6
7
8
9
10
11
-- Problem 8
compress :: Eq a => [a] -> [a]
compress (x:ys@(y:_))
| x == y = compress ys
| otherwise = x : compress ys
compress ys = ys

compress' [] = []
compress' (x:xs) = x : compress' (dropWhile (== x) xs)

compress'' x = foldr (\a b -> if a == head b then b else a:b) [last x] x

Problem 9

(**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example:

1
2
* (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:

1
2
3
λ> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 
'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]

Solutions

1
2
3
4
5
6
7
8
9
-- Problem 9
pack :: Eq a => [a] -> [[a]]
pack [] = []
pack xs@(x:_) = takeWhile (==x) xs : pack (dropWhile (==x) xs)

pack' [] = [] -- group in Data.List
pack' (x:xs) =
let (first, rest) = span (==x) xs
in (x:first) : pack' rest

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:

1
2
* (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:

1
2
λ> encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

Solutions

1
2
3
4
5
-- Problem 10
encode :: Eq a => [a] -> [(Int, a)]
encode = map (\xs -> (length xs, head xs)) . pack

encode' xs = [(length x, head x) | x <- pack xs] -- List comprehension
------ 本文结束------
0%