11.7 練習問題
- ライブラリ関数
concatとmapを用いる代わりに、リスト内包表記を使って、組み合わせの関数choicesを再定義せよ。
10章の練習問題でリストモナドについて書いたことを思い出せば簡単。
choices' :: [a] -> [[a]] choices' xs = [zs | ys <- subs xs, zs <- perms ys]
- 再帰的な関数
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
- 関数
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の中で無視されるから、たいした影響はないはず……と思ったんだけど、実行してみると逆にちょっと速くなる。何で？
