SSブログ

Haskell でいろいろと列挙する [Haskell]

* 自然数を列挙する

[1..]

* 正の奇数を列挙する

[1,3..]

* 整数(負の数を含む)を列挙する

ほぼ [1] の記事からの引用。ゼロが特別扱いで後つけになる。

0:[ s * x | x <- [1..], s <- [1, -1] ]

* 正の整数の対を列挙する

[2] の論文の冒頭で「遅延評価の関数型言語のプログラマならみんな知っている方法」(本当ですか?)として挙がっていたのをちょっと改変した(有理数じゃなく整数の対にしただけ)のがこれ。

intPairs :: [(Integer, Integer)]
intPairs = concat (diags [[(m, n) | m <- [1..]] | n <- [1..]])

diags = diags' []
          where diags' xss (ys:yss) = map head xss:diags' (ys:map tail xss) yss

私は関数が適用される様子をノートに書いてじっくり考えないと分かりませんでした。

でもこれって以下のように書いたほうが直接的で分かりよくないだろうかと思った。(あと上の方法って数が大きくなるにつれてメモリ使用量が上がっていくような気もするのだがこれは検証していない)

intPairs2 :: [(Integer, Integer)]
intPairs2 = iterate nextIntPair (1, 1)

nextIntPair :: (Integer, Integer) -> (Integer, Integer)
nextIntPair (x, y) | x == 1    = (y + 1, 1)
                   | otherwise = (x - 1, y + 1)

* 整数(負の数を含む)の対を列挙する

2次元座標をぐるぐる巻きになぞるようにしてみた。もっと賢い書き方がきっとありそう。

intPairs3 :: [(Integer, Integer)]
intPairs3 = iterate nextIntPair3 (0, 0)

nextIntPair3 :: (Integer, Integer) -> (Integer, Integer)
nextIntPair3 (0, 0) = (1, 0)
nextIntPair3 (x, y) | x > 0 && (abs x) >  (abs y) = (x, y - 1)
                    | y > 0 && (abs x) <= (abs y) = (x + 1, y)
                    | x < 0 && (abs x) >= (abs y) = (x, y + 1)
                    | y < 0 && (abs x) <= (abs y) = (x - 1, y)

* 使い道

数学的センスが無い私のような人が問題をコンピュータにブルートフォースで解かせるのに役立ちます。

問題: 82r + 17s = 1 を成立させるような整数 r,s を1組挙げよ

Main> take 1 [(r, s) | (r, s) <- intPairs3, (82 * r) + (17 * s) == 1]
[(-6,29)]

ちなみに [2] の論文のメインは重複しない正の有理数を列挙する方法についてのものですが、私はまだ読んでいません。同じアルゴリズムを以前結城浩さんが「既約分数クイズ」[3] として紹介してブーム?になったそうです。

[1] http://haskell.g.hatena.ne.jp/hyuki/20060621/lc
[2] http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf
[3] http://www.hyuki.com/diary/dia0312.html#i30


Haskell でドント方式の議席数配分 [Haskell]

「どう書く?org - 議席数をドント方式で」 [1] 用に、これは無限リストだなーと思って Haskell で書いたのだけど書いているうちに先を越されて、それより発想が違うわけでも短いわけでもなかったので(でも読みやすいかも)投稿せずにこっちにおいておくことにした。

type Party = Int
type Votes = (Rational, Party)

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x > y = x:merge xs (y:ys)
merge (x:xs) (y:ys) | x < y = y:merge (x:xs) ys
merge (x:xs) (y:ys) | x == y = x:y:merge xs ys

mergeList :: Ord a => [[a]] -> [a]
mergeList = foldl merge []

voteSeq :: Votes -> [Votes]
voteSeq (v, n) = [((v / x), n) | x <- [1..]]

toVotes :: [Rational] -> [Votes]
toVotes vs = zip vs [1..]

dhondtSeq :: Int -> [Votes] -> [Votes]
dhondtSeq limit vs = take limit $ mergeList [voteSeq x | x <- vs]

numSeat :: Party -> [Votes] -> Int
numSeat p vs = length [x | (x, n) <- vs, n == p]

dhondt :: Int -> [Rational] -> [Int]
dhondt limit vs =
  [numSeat n ds | n <- [1..length vs]]
     where vs' = toVotes vs
           ds = dhondtSeq limit vs'

merge と mergeList はひょっとしたら標準関数を再発明しているかもしれない。
あと Haskell で有理数を使うのは単に Rational って型を書けばよいだけだということを知ったので前回の小町算も Float じゃなくて Rational にすればよかった。

[1] http://ja.doukaku.org/26/


Haskell で小町算 [Haskell]

前回 Lua で挑戦した小町算 [2] に今度は Haskell で挑戦して見たいと思います。どうやって考えたかも含めて説明していきます。

続きを読む


"Programming in Haskell" by Graham Hutton を読んだ [Haskell]

大学1年生にも教えられますという謳い文句?の Haskell 本。最終章以外大体読み終わったので感想など。

第1印象としては、この本は見開きの左右がそれぞれ3分の1くらい余白になっていて、そこが良いと思った。註は一切ないのでこれは書き込み用の余白を拡げてくれているのだろう。

教育的な本では概念を登場させる順序というのが命で、殆どそれだけで成否が決まるといっても過言ではないけど Haskell の場合は入出力をどこでどう登場させるかというのが最大の問題になると思う。「後で説明するから今はおまじないだと思って読んでね」というのも手ではあるけどこれは学習者の意欲を削ぐ結果になるかもしれない。

この本ではどうしているかというと、まず最初のうちは Hugs を使ってインタラクティブシェル上でプログラミングする。これで入出力のことはしばらく考えずに進めることができる。
入出力が出てくるのは第9章だが、実はその1つ前に Functional Parsers という章があって、そこでパーサを組み立てていく過程で Parser 型とそれに対する return 関数、>>= 演算子を定義して、do 構文もそこで導入している。そうすることで後で IO 型を導入するときに前章の Parser 型になぞらえて理解ができるように準備しているのだ。そしてさらに後の章になって Parser 型と IO 型の類似は実は偶然じゃなくて Monad クラスによって一般的に捉えられるよ、という風に進む。
私はこの構成は理解しやすいと思った(やっとわかった気になった)。他の点でも順序がよく練られている印象がある(遅延評価の話が出るのがずいぶん遅くて、それが何でかなと思った以外は)。

一方この本で1つ嫌いだった部分は、著者は Maybe a 型の変わりに [a] 型(a のリスト型)を使うのが好みのようで(Nothing を空リスト、Just を1要素リストで表す)、Maybe を導入した後ですらその書き方を使う。曰く、リスト内包表記を使って簡潔に書けるからだそうで、この人はリスト内包表記に1章を費やすくらいリスト内包表記好きらしい。
Haskell 界でこういう書き方が一般的なのかどうか分からないけど、リスト型がこういう風に使われているかもしれないということになったら [a] 型を見るたびにそれが Maybe 型の代わりなのか本当にリストなのかを考えないといけなくなる。
例えば著者が上記の弁明をした次のページに [a] -> [([a], [a])] という型が出てくるが、この型の本当の意味が 2^4 通りのうちどれなのかは説明かコードを読まないと分からないということになってしまう。これは学習者の邪魔をしているだけだし、型で考えるということの模範にならないと思う。

あとコード中の表記でわざわざ \ じゃなくてλって書いたり ^ じゃなくて↑って書いたりするのは何なんだろうと思った。The Reasoned Schemer もひどいものだったことを思い出したけど、海外にはこういう主義の人が一定数いるんだろうか。

とはいえ全体としてみれば入門書としてのこの本の分かりやすさはすばらしいと思う。私のような文系頭の人間でも困難を感じずに読める。


ラムダ文字の由来 [Haskell]

Haskell で匿名関数を表現するのに \ を使うのはバックスラッシュがラムダ文字 λ に似てるかららしい。でもこれは Windows とかだと円記号になってしまって台無しである。それにバックスラッシュは相当多くの言語で一意にエスケープの意味を持つので混乱する。

匿名関数をラムダ lambda と呼ぶのは Lisp の影響だが、Peter Norvig の Paradigms of Artificial Intelligence Programming によると Lisp で匿名関数を lambda と書くのは以下のような由来らしい。

- Russel と Whitehead の Principia Mathematica では のように束縛変数の上にキャレットを置く書き方をしていた
- Church がその記法を ^x(x+x) と変えた
- キャレットの下に何も無いのが変だと思ったので形が似ている Λx(x+x) と変えた(大文字ラムダ)
- やっぱり Λ は他の記号と見間違えやすいので小文字にして λx(x+x) とした
- McCarthy が Lisp を作ったときにそのラムダ表記を借りて lambda とした

Haskell も Church の最初の記法にさかのぼればよかったのになあと思った。


n+k パターン [Haskell]

Haskell には n+k パターンというのがあって、パターンマッチのパターンの部分に n+2 みたいな形式をおけるらしい。
こんなコードを試してみた。

f (n+2) = "match: " ++ (show n)
f _     = "unmatch"

main = do
  putStrLn (f 3)
  putStrLn (f 2)
  putStrLn (f 1)
  putStrLn (f 0)

そうするとこうなる。

match: 1
match: 0
unmatch
unmatch

つまり n+2 というパターンは 2 以上の値にマッチして n はそこから 2 を引いた値に束縛される、ということだ。へ~。

ただ、へ~と思っただけで、要るか?と言われたら特に要らない気もします。


この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。