mapAccumL, mapAccumR を使った書き換えに挑戦。
@so_zaneli Problem 24. 十進表記の場合、例えば 123 を 10 で割って余り 3、商の 12 を 10 で割って余り 2、商 1 が出て終了、的な考えで、最初は 2 で割って、次は 3 で割って、次は 4 で割って、... とやるとシンプルかも。
— [1..100]>>=pen (@1to100pen) 2014, 1月 14
@so_zaneli (100万-1)を2で割った余りは1、その商の方を3で割った余りは1、さらにその商を4で割った余りは2、さらに...とやって余りを右から並べると[2,6,6,2,5,1,2,1,1,0]という数列ができます(最初の余りは0としとく)。これを使うと
— [1..100]>>=pen (@1to100pen) 2014, 1月 14
@so_zaneli Problem 24. 十進表記の場合、例えば 123 を 10 で割って余り 3、商の 12 を 10 で割って余り 2、商 1 が出て終了、的な考えで、最初は 2 で割って、次は 3 で割って、次は 4 で割って、... とやるとシンプルかも。
— [1..100]>>=pen (@1to100pen) 2014, 1月 14
@so_zaneli (100万-1)を2で割った余りは1、その商の方を3で割った余りは1、さらにその商を4で割った余りは2、さらに...とやって余りを右から並べると[2,6,6,2,5,1,2,1,1,0]という数列ができます(最初の余りは0としとく)。これを使うと
— [1..100]>>=pen (@1to100pen) 2014, 1月 14
むむっ…よくは分からんがとりあえず試してみよう。文章をコードに落とし込んでみるぞ!
うーむ、こうなった…。
ちゃんと動いてくれているな…。
mapAccumL, mapAccumR
mapAccumL
とmapAccumR
について、初めて使ってまだよく理解していないのでもう少し詳しくみていこう。> :t mapAccumL mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) > :t mapAccumR mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])ふむ。
使ってみる。
> mapAccumL (\acc x -> let sum = acc + x in (sum, show acc ++ " + " ++ show x ++ " = " ++ show sum)) 0 xs (15,["0 + 1 = 1","1 + 2 = 3","3 + 3 = 6","6 + 4 = 10","10 + 5 = 15"]) > mapAccumR (\acc x -> let sum = acc + x in (sum, show acc ++ " + " ++ show x ++ " = " ++ show sum)) 0 xs (15,["14 + 1 = 15","12 + 2 = 14","9 + 3 = 12","5 + 4 = 9","0 + 5 = 5"])ふむふむ。
ペアのfstにアキュムレータを畳み込んで行って、ペアのsndに計算途中の(アキュムレータとは異なる)値を追加していく、
foldl, foldr
とscanl, scanr
の合わせ技的な関数、という理解で良いのかな?例えば
> mapAccumR divMod 99999 [10,9..1] (0,[0,2,3,5,5,1,2,1,1,0])は
> 99999 `divMod` 1 (99999,0) > 99999 `divMod` 2 (49999,1) > 49999 `divMod` 3 (16666,1) > 16666 `divMod` 4 (4166,2) > 4166 `divMod` 5 (833,1) > 833 `divMod` 6 (138,5) > 138 `divMod` 7 (19,5) > 19 `divMod` 8 (2,3) > 2 `divMod` 9 (0,2) > 0 `divMod` 10 (0,0)上記のような計算手順を経て、各divModのfst(つまり商)を次の計算に渡しつつ、snd(つまり剰余)をリストに追加していく。
リストから要素を取り出す
リストとindexを指定して、そのindexにあたる要素と、その要素を取り除いた新しいリストを返す関数がData.List あたりに用意されていてもよさそうに思ったけど、どうやら無いらしい。
今回はリスト内に同一要素が無い事が分かっているため
f xs i = let x = xs !! i in (delete x xs, x)
としたが、本来ならこんな関数を用意したほうがよさそう。
(<-|) :: Int -> [a] -> (a, [a]) n <-| xs = let (l, h:t) = splitAt n xs in (h, l ++ t)
> 1 <-| [1,2,3,4,5] (2,[1,3,4,5])