Changes in body
Source | HTML | Preview

から[1..10]

まずは解答を見ないでチャレンジ、そのあと解答を見てみて面白そうな実装があればいろいろ試してみた

まずは言語の概要をつかめるように、こういう問題集の存在はありがたいと思う。

# リストの最後の要素を求めよ。

last関数を実装したら良い、のでパターンマッチで書き下す。
カリー化されたsnd関数を畳み込むのは面白いと思った。

prob01.lhs
``````
Find the last element of a list.

> myLast :: [a] -> a
> myLast [] = error "the input list is empty"
> myLast [x] = x
> myLast (x:xs) = myLast xs
> -- myLast (_:xs) = myLast xs

Use the place holder:

myLast (_:xs) = myLast xs

An interesting implementation from the solutions:

curry' :: ((a, b) -> c) -> a -> b -> c
curry' f x y = f (x, y)

curry snd :: a -> c -> c

foldl1 :: (a -> a -> a) -> [a] -> a

> myLast' :: [a] -> a
> -- myLast' = foldl1 \$ curry snd
> myLast' = foldl1 (curry snd)

This implementation continuously takes "second" element.
So, this will fail when applied on empty list.
For singleton list, the following behavior is guaranteed by the definition of foldl1:

> foldl1' :: (a -> a -> a) -> [a] -> a
> foldl1' f [x]    = x
> foldl1' f (x:xs) = foldl f x xs

So, we get

myLast' [1] = foldl1 (curry snd) [1]
= 1

Another interesting implementation is the following:

> myLast'' :: [a] -> a
> myLast'' = foldr1 (const id)

const :: a -> b -> a
const id :: b -> a -> a

The same rule holds for singleton list, and for longer list,

myLast'' [1,2,3] = foldr1 (const id) [1,2,3]
= (const id) 1 \$ foldr1 (const id) [2,3]
= (const id) 1 \$ (const id) 2 \$ 3
= (const id) 1 \$ 3
= 3
``````

foldl1 とfoldlr1 のsingleton list における挙動が最初わからなかったけど、よく考えたら頭かおしりの要素をaccumulator として採用するのでそのまま帰るわけですね。

# リストの最後から２番目の要素を求めよ。

これも方針はパターンマッチ。

prob02.lhs
``````Find the last but one element of a list.

Pattern match

> myButLast :: [a] -> a
> myButLast [x,_]  = x
> myButLast (_:xs) = myButLast xs
> myButLast _      = error "need 2 or more elements"

*Main> head . tail \$ "aiueo"
'i'

It is always good to use built in functions, but keep in mind that it might fail due to the emptylist.

> myButLast' :: [a] -> a
> myButLast' = head . tail . reverse
``````

# リストのK番目の要素を求めよ。

(!!)の実装ということに気がついたら、原点をずらすだけでできるけど。

prob03.lhs
``````Find the K'th element of a list.
The first element is the list is number 1.

> elementAt :: [a] -> Int -> a
> elementAt (x:_)  1 = x
> elementAt (_:xs) n = elementAt xs (n-1)
> elementAt _      _ = error "Index out of bounds"

Implicitly assumed the number is less than the length of the list!

> elementAt' [] _ = error "Index out of bounds"
> elementAt' (_:xs) n
>   | n <= 0    = error "Index out of bounds"
>   | otherwise = elementAt' xs (n-1)

Using an infix operator !!,

> elementAt'' :: [a] -> Int -> a
> elementAt'' lst n = lst !! (n-1)

Let's take a moment,

[(1,'h'),(2,'a'),(3,'s'),(4,'k'),(5,'e'),(6,'l'),(7,'l')]
*Main> filter (\(n,c) -> n == 5) it
[(5,'e')]
*Main> snd . head \$ it
'e'

> elementAt''' lst n = snd . head \$ filter (\(m,_) -> m == n) \$ zip [1..] lst

``````

せっかくだから別解を作ろうと思って考えたのが最後の実装、1 から始まるインデックスならzip [1..] が思いついたのでなんとか使えないかなと。
ワンライナーで書くと分かりにくいきもするけど、実験結果の貼り合わせだからまぁ良しとする。

# リストの要素数を求めよ。

lengthの再実装。
フィボナッチ数列の問題か何かで累算器を使ったのを覚えていたので。

prob04.lhs
``````Find the number of elements of a list.

> myLength :: [a] -> Int
> myLength lst = myLength' lst 0
>   where myLength' []     n = n
>         myLength' (_:xs) n = myLength' xs (n+1)

This n is so-called the accumulator.

> myFoldlLength :: [a] -> Int
> myFoldlLength = foldl (\n _ -> n+1) 0

*Main> zip [1..] "aiueo"
[(1,'a'),(2,'i'),(3,'u'),(4,'e'),(5,'o')]
*Main> fst . last \$ it
5

> myZipLength :: [b] -> Int
> myZipLength = fst . last . zip [1..]

> my1Length :: [a] -> Int
> my1Length = sum . map (\_ -> 1)
``````

この辺でfold を使った実装に型注釈が無いとghci が文句言うのに気がついてきた、なんとなくリストのみ考えているからいけないわけでFoldable のリストインスタンスのみに限って実装してるのを意識しないといけない。

# リストを逆順にせよ。

reverseの再実装。

コメントにもあるけど、効率は良くないらしい。

prob05.lhs
``````Reverse a list.

> myReverse :: [a] -> [a]
> myReverse [] = []
> myReverse (x:xs) = (myReverse xs) ++ [x]

This definition is more waseful than the standard definition in Prelude.
The standard definition, found in the prelude, is concise but not very readble:

reverse = foldl (flip (:)) []

Using accumulator, we can dramatically reduce the order from O(n^2) to O(n)!

> myReverse' :: [a] -> [a]
> myReverse' lst = myReverse' lst []
>   where myReverse' []     tsl = tsl
>         myReverse' (x:xs) tsl = myReverse' xs (x:tsl)

This is so-called Bustall-Darlington transformation, see 4.1.5 of Algorithms: A Functional Programming Approach (Fethi Rabhi, Guy Lapalme).
``````

# リストが回分かどうか判定せよ。

pの最初の引数はリストが逆順に積まれていって、２つ目の引数はリストの後ろの方だけが残っていく。

prob06.lhs
``````Find out whether a list is a palindrome.
A palindrome can be read forward or backward; e.d. (xamax).

> isPalindrome :: Eq a => [a] -> Bool
> -- isPalindrome lst = (myReverse lst == lst)
> isPalindrome lst = (myReverse' lst == lst)
>
> myReverse' :: [a] -> [a]
> myReverse' xs = helper xs []
>   where helper []     y = y
>         helper (x:xs) y = helper xs (x : y)

myReverse is from prob05.lhs

A nicer implementation is the following, it only flips the half:

> isPalindrome' xs = p [] xs xs
>   where p rev (x:xs) (_:_:ys) = p (x:rev) xs ys
>         p rev (x:xs) [_]      = rev == xs
>         p rev xs     []       = rev == xs

rotor
p [] rotor rotor
p r otor tor
p or tor r
==> r==r = True

boneanob
p [] boneanob boneanob
p b oneanob neanob
p ob neanob anob
p nob eanob ob
p enob anob []
==> enob /= anob = False
``````

# ネストされたリストを解(ほど）け。

flatten の訳語がいまいちわからなかった。

さっぱりわからなかったので解答をコピペ。

prob07.lhs
``````
Flatten a nested list structure.

We have to define a new data type, because lists in Haskell are homogeneous.

> data NestedList a = Elem a
>                   | List [NestedList a]
>
> myFlatten :: NestedList a -> [a]
> myFlatten (List [])     = []
> myFlatten (Elem x)      = [x]
> myFlatten (List (x:xs)) = myFlatten x ++ myFlatten (List xs)
> -- myFlatten (List [])     = []

Just a copy and paste of the solutions.

Simple implementation using
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
is the following:

> myFlatten' :: NestedList a -> [a]
> myFlatten' (Elem x) = [x]
> myFlatten' (List x) = concatMap myFlatten' x

> myFlatten'' :: NestedList a -> [a]
> myFlatten'' (Elem x) = return x
> -- myFlatten'' (List x) = myFlatten'' =<< x
> myFlatten'' (List x) = x >>= myFlatten''

flatten3 :: NestedList a -> [a]
flatten3 (Elem x ) = [x]
flatten3 (List xs) =  foldr (++) [] \$ map flatten3 xs
``````

# リストのうち連続して同じものがあれば一つを残してそれ以外を取り除け。

dropWhileを思いつかなかった。
リストに関する備え付けの関数は一度は触る価値がありそう、と思いこのへんからMiran Lipovacaを読み出す。
アルゴリズムはすなわち、かぶりがあれば先頭だけ残して残りを落としたリストにcons(:)でくっつけていく再起。
したがってfoldrでも書ける、と思う。

prob08.lhs
``````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.

> compress :: Eq a => [a] -> [a]
> compress [] = []
> compress (x:xs) = x : (compress (dropWhile (== x) xs))

This is also copy and paste.
It's nice to use dropWhile

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p xs@(x:xs')
| p x        = dropWhile p xs'
| otherwise  = xs

compress' [] = []
compress' [x] = [x]
compress' (x:y:ys)
| x == y    = x : (compress' ys)
| otherwise = x : (compress' (y:ys))

This does not work correctly, but I can fix it:

> compress'' :: Eq a => [a] -> [a]
> compress'' [] = []
> compress'' [x] = [x]
> compress'' (x:y:ys)
>   | x == y    = compress'' (y:ys)
>   | otherwise = x : (compress'' (y:ys))
``````

リストを使った集合の実装の際に使えそうな下処理である、すなわち外延性公理から集合の要素のダブリは集合同士の等号には効かないので、ダブリがないものを選べる、という話である。
これまた再度読みなおしただけ。

# リスト内に連続した重複あればサブリストにまとめよ。

dropWhileを使ったのでtakeWhileも使いましょうという感じだろうか？

dropWhileは(==x)の判定が擬になった時点で止まるので、連続していなければ落とされずに済む。

prob09.lhs
``````Pack consecutive duplicates of list elements into sublists.
If a list contains repeated elements they should be placed in separate sublists.

> pack :: Eq a => [a] -> [[a]]
> pack [] = []
> pack (x:xs) = (x:front) : pack rear
>   where front = takeWhile (== x) xs
>         rear  = dropWhile (== x) xs

Slightly modifed version of the solution.

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] =  []
takeWhile p (x:xs)
| p x        = x : takeWhile p xs
| otherwise  = []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] =  []
dropWhile p xs@(x:xs')
| p x        = dropWhile p xs'
| otherwise  = xs
``````

これもまた特にネタなし、解答例にも面白いの無いなぁ。。。

# リスト内の重複とその数を数えよ。

やはり高階関数のmapは便利である。

prob10.lhs
``````Run-length encoding of a list.
Use the result of prob09.lhs 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.

> import Data.List (group)

> encode :: Eq a => [a] -> [(Int, a)]
> encode lst = map encode' (pack lst)
>   where encode' xx@(x:xs) = (length xx, x)
>
> pack :: Eq a => [a] -> [[a]]
> pack [] = []
> pack (x:xs) = (x:front) : pack rear
>   where front = takeWhile (== x) xs
>         rear  = dropWhile (== x) xs

pack is in prob09.lhs

Or writing it pointfreestyle (Note that the type signature is essential here to avoid hitting the Monomorphism Restriction):

["aaaa","b","cc","aa","d","eeee"]
*Main Data.List> map (\x -> (length x, head x)) it
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

> pointfreeEncode :: Eq a => [a] -> [(Int, a)]
> pointfreeEncode = map (\x -> (length x, head x)) . group
``````

Data.List のgroup を知っていると簡単な実装が出来ますね、注意書きの Monomorphism Restriction の件が分からないところですが。