Posted at

Haskellで減少配列の動きが理解できなかったけど頑張って理解できた話

対した話でもないので自分用のメモ書きみたいなものですが…。


発端


Learn You a Haskell for Great Good!


これの日本語翻訳された書籍版(すごいHaskell楽しく学ぼう!)があってそれを読んでHaskell入門をしていたわけですが、

1章のRangeに関する部分で 減少列 についてが出てきたんですよね。

簡単に言うと減少列は例えば10から1までの1づつ減っていく配列のこと。

普通に増えていく配列、増える数を指定して増やす配列までは理解がまぁできた。

だけど減少列に関する部分だけ、なんでこの書き方でこうなるの???と

完全に :Thinking_face: をしていたわけですね。:thinking:

自分で自分にggrksしてもぜんぜんどうしてなのか書いてあるサイトが見つからないし。 (調べ方が下手なだけかも)

それで書籍・GHCIとおよそ二日ほどにらめっこしてたわけですが

それでようやく自分で理解できる解を見つけたので忘れないうちに書き記しておこうと思いここに書くことにしました。


リストでのRange


  • 通常のRange


  • ステップ付きRange


  • 減少Range


の3種類の説明を一応書いときます。

書籍文中より軽く引用すると


通常のRange


1から20の全ての自然数を含むリストを作るには、 [1..20] とタイプするだけです。

Haskellでこれは

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

とタイプするのと全く同じことです。

これら2つの書き方の唯一の違いは、長い列挙列を手で入力するのはバカげてる、ってことです。


これは普通に書いてある通り1から20までの整数を配列にぶち込んで生成するRange。

全然普通に理解できる。


ステップ付きRange


レンジにはステップを指定することもできます。

1から20までの全ての偶数のリストが欲しいときはどうすればいいでしょうか?

あるいは1から20までの全ての3の倍数は?

最初の要素と二つ目の要素をカンマで区切って、上限を指定するだけです。

ghci> [2,4..20] 

[2,4,6,8,10,12,14,16,18,20]
ghci> [3,6..20]
[3,6,9,12,15,18]

ステップとして2を指定したら2づつ、3なら3づつで次は4..20・3..20と指定してやれば2と3それぞれの倍数取れるのね、とこの時自分は解釈した。

が、実はこの解釈の仕方も実際の動きとはまた違ったものだった。


減少Range


20から1までの減少列を作るためには、 [20..1] ではなくて、 [20,19..1] と書かなければなりません。

ステップなしで( [20..1] のように)レンジを書いた場合、Haskellは空リストから始めて、最初の要素が最後の要素より大きくなるまで要素を列挙します。

20は既に1より大きいので、結果はただの空リストになります。


この説明を読んだ時点でもだいぶ頭に???が浮かんでいた。

書き方をそのまま真似すれば確かに同じように減少列が作れるだろうけど、どうしてステップ付きでそう指定しなければ動かないのかが全く理解できなかった。


ステップを付与したときのRangeの動き方

結局のところどういうことなのっていうと

仮にリストとして

[x,a..b]

があるとして


  • 間違った解釈(過去の自分)

ステップとして x を指定して ax を一回足したしたものを次々とリストにぶち込んでいく。

最終的に (a + x) > b になったら終わる。


  • 正しい(はず)の解釈

ステップとして設定された x と 範囲 a の差分(仮に y としておく)を a に足してそれをリストにぶち込んでいく。

yy = a - x で求められる

最終的に (a + y) > b になったら終わる。

(減少列の場合は (a + y) < b なのか?ここだけちょっと曖昧)

そういうことね!!!!!

これが理解できた時マジで脳汁溢れそうだった。


結論として

最初に自分がそうだと思っていた1番目の動きでいくとどうしても減少列として作ったときにそうはならんやろとなってしまう。

ついでに言えば [2,2..20] としたとき2づつ増えると思ってたのになぜか配列が [2,2,2,2,2,2...] で無限ループしてしまうのにも納得がいかなかった。

けれど2番目の動きが正しいとすれば [10,9..1] のとき 9 - 10 した結果の-1をどんどん10に 足して いけば結果的に10から1までの減少列となる。

[2,2..20] であれば 2 - 2 = 0なので2を配列に入れ続け無限ループに入る。

普通のステップ付きレンジではあるけど [2,5..20] なんかであれば 5 - 2 = 3 なので3を足しながら増えていくので

配列としては [2,5,8,11,14,17,20] となる。


おわり

いかがでしたか? おい

レンジとしてどう配列にぶち込まれるのかの動きを完全に勘違いしていましたというお話。

解が出ると自分でなんであんなに悩んでたんだろうとなるくらいには単純な動きだった。

そして全てに納得がいった。

すごいHaskellたのしく学ぼう!本こと、すごいえっち本はまだ2章を読み始めたくらいしか読んでないのでこれから頑張ろうと思います。