第11章 切符番号遊び #2

11.7 練習問題

1. ライブラリ関数concatとmapを用いる代わりに、リスト内包表記を使って、組み合わせの関数choicesを再定義せよ。

10章の練習問題でリストモナドについて書いたことを思い出せば簡単。

choices' :: [a] -> [[a]]
choices' xs = [zs | ys <- subs xs,
                    zs <- perms ys]

2. 再帰的な関数isChoice :: Eq a => [a] -> [a] -> Boolを定義せよ。この関数は、関数permsや関数subsを使わずに、一方のリストが他方のリストから選択されたものかを検査する。
   ヒント：まずはじめに、あるリストに対して、最初に見つかった特定の値を取り除く関数を定義せよ。

というわけでヒントどおりに関数eliminateを定義する。 最初はfilterでいいかと思ったがそれではダメ。「最初に見つかった」値だけを取り除かないといけないから。

eliminate :: Eq a => a -> [a] -> [a]
eliminate p ps = before ++ after
  where
    before = takeWhile (/=p) ps
    after  = safeTail (dropWhile (/=p) ps)
    safeTail []   = []
    safeTail x:xs = xs

（追記）なんて無駄なコードを……疲れてたのだろうか。消してしまいたい。

eliminate :: Eq a => a -> [a] -> [a]
eliminate _ [] = []
eliminate x (y:ys)
  | x == y    = ys
  | otherwise = y : eliminate x ys

で、これを使うとこんな感じか。第1引数が選択元、第2引数が選択結果としよう。

isChoice :: Eq a => [a] -> [a] -> Bool
isChoice _  [] = True
isChoice [] _  = False
isChoice xs (y:ys)
  | not (elem y xs) = False
  | otherwise       = isChoice (eliminate y xs) ys

3. 関数splitを空リストも許すように拡張すると、関数solutionsの挙動にどのような影響を与えるか述べよ。

空リストを許すということは、こんな定義？

split        :: [a] -> [([a],[a])]
split []     =  ([], [])
split [x]    =  ([], [x])
split (x:xs) =  ([], (x:xs)) : [(x:ls,rs) | (ls,rs) <- split xs]

splitの結果に要素が1つ増えるだけだし、しかもそれは空リストを含んだタプルなので、exprsの中で無視されるから、たいした影響はないはず……と思ったんだけど、実行してみると逆にちょっと速くなる。何で？