- 関数型プログラミング言語Haskell Part27＿©2ch.net
15 ：デフォルトの名無しさん[sage]：2015/01/11(日) 01:53:57.06 ID:q/YrvBDO - 下記の問題について自分なりにプログラムしてみましたが、
問題の性質を静的に（宣言的に）表しているとは言い難いような気がします。
その性質自体がいくぶん動的な体をしているので仕方ないかも知れませんが。
皆さんなら、どのようにプログラムするでしょうか。
[問題]
型aの値には「大きさ」という属性があり、それは関数 (HaveSize a) => size :: a -> Int で得られる。
ただし戻り値は正の整数で、また、size x = size y となる x, y ∈a も存在する。
問題は、型 [a] の値と大きさ n（非負正数）のコンテナがあるとき、
[a] の要素を左から順にコンテナに溢れ出ないように詰め込んでいった場合に
どれだけの部分リストが詰め込めるかを調べる関数 saturate を作ること。
[例]
map size [a, b, c, d, e] = [2, 1, 3, 2, 3] とする。
コンテナの大きさが 7 なら、[a,b,c] がコンテナに詰め込める。
なぜなら [a, b, c] の大きさの合計が 2+1+3=6 で、
更に d を詰めようとすれば 6+2=8 になりコンテナの大きさを超えるからである。
コンテナの大きさが 6 の場合も同じく [a, b, c] まで詰め込める。
コンテナの大きさが 1 以下なら詰め込める部分リストは空リスト [] である。
[私の解答例]
saturate :: (HaveSize a) => Int -> [a] -> (Int, [a])
saturste _ [] = (0, [])
saturate n (x:xs)
| n < s = (0, [])
| otherwise = (s, x) +: saturate (n - s) xs
where s = size x
infixr 5 +:
(+:) :: (Int, a) -> (Int, [a]) -> (Int, [a])
(m, x) +: (n, xs) = (m + n, x: xs)
|