blog.PanicBlanket.com

『本物のプログラマはhaskellを使う』にでてきた用語の日英対応表をつくってみた。
こういうのは憶えておくと役に立つ，かも。

lazy evaluation	遅延評価，怠惰評価
functional programming	関数型プログラミング
logic programming	論理型プログラミング
probabilistic functional programming	確率的関数プログラミング
Domain Specific Language	特定領域言語，ドメイン特化言語
lambda abstraction	ラムダ抽象
anonymous function	無名関数
type inference	型推論
type variable	型変数
context	文脈
type class	型クラス
instance	インスタンス
inheritance	継承
subclass	サブクラス
module	モジュール
import	インポート
type synonym	型の同義名，型シノニム
algebraic data type	代数的データ型
type constructor	型構成子，型構築子
data constructor	データ構成子，データ構築子
polymorphic type	多相型，多様型
parametric polymorphism	パラメータ多相，パラメトリック多相
ad-hoc polymorphism	アドホック多相
unboxed array	非ボックス化配列
infix operators	中置演算子
monad	モナド
action	動作，アクション
bind	束縛した
do expression	do式
do-notation	do記法

　cf. 結城浩のHaskell日記 – type宣言

とりとめもない話なんだけど。
エントリのなかに isPrefixOf という関数がでてくる。

xs `isPrefixOf` ys

は文字列 xs が ys のプレフィックスである時に True を返すんだけど，この xs と ys の順序について。

上のように中置形式で書くという前提なら，「xs が ys のプレフィックスのとき True」というのは素直に納得できる。
じゃあ，普通に関数名を前に置いて書いたらどうか。

isPrefixOf xs ys

これって見た目には，どちらかというと「ys が xs のプレフィックスのとき True」，つまり中置き形式のときとは逆じゃないかな。さらに，部分適用してこんな関数を考えてみるとなおさらそんな気がする。

isPrefixOfXS = isPrefixOf "is it prefix of xs?"

いや，こんな関数はあまり有用には思えないからいい例じゃないんだけど。

前置も中置もどちらもおなじ，というのを合わせて考えると，引数の順序もなんだか悩ましいなぁ，と。

夕べ帰ったらAmazon.co.jpから届いていた。

[amazonjs asin=”4797373970″ locale=”JP” title=”ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門”]

だけど，今週はちょっと読む時間がない。
『入門Haskell―はじめて学ぶ関数型言語』 もまだ消化しきれてないし。
まぁ，焦っても仕方がない。ゆっくり行こう。

結城浩のHaskell日記にコメントをつけようとしたら，グループに参加しろと（はてなが）言うので参加してみた。
せっかくなので Haskellリング にも参加。

みなさん，よろしくお願いします。

下のエントリは前段でこっちが本題。id:hyukiさんとこにコメントをつけたんだけど，忘れないようにこっちにも書いておく。

filter' f xs = foldr (\m n -> if f m then m:n else n) [] xs

結果。

*Main> take 50 $ filter' odd [1..]
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,
57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99]

リスト中に，関数 f（述語って言うの？）を満たす要素のほうが多ければ True をかえす，というのを考えた。all と any の中間みたいなもの。

major f xs = (length $ filter f xs) > (length $ filter (not . f) xs)

結果。

*Main> major odd [1..5]
True
*Main> major even [1..5]
False

地道に数を数えるならこうかな。

major f xs = fst count > snd count
  where count = foldl (\(ct, cf) x -> if f x then (ct+1, cf) else (ct, cf+1)) (0,0) xs

*Main> major odd [1..5]
True
*Main> major even [1..5]
False

レコードは代数的でないデータ型。C の構造体のようなもの。うまい例を思いつかないから，本に載ってるのをそのまま書くとこんな感じ。

data Point = Pt {x :: Integer, y :: Integer}

x，y をフィールドといい，それぞれ Integer 型の値を取る。具体的に値を定義するにはこうする。

Pt { x = 1, y = 4 }

代数的データ型を使っても同じようなことはできる。データ構成子が複数の引数を取ることにすればいいし，タプルにしてもいい。これらとレコードが違うのは２点。

• 名前がついているのでわかりやすい。
• フィールド名が，同時にフィールドにアクセスするための関数になっている。

２つ目のほうはこんな感じだ。

*Main> x Pt {x = 2, y = 3}
2

x という関数が定義されてるってことだな。

*Main> :t x
x :: Point -> Integer

さて，じゃあおなじフィールド名を持つレコードを宣言するとどうなるか。

data TP = Tp { x :: Int, y :: Int } deriving (Eq, Show)

data Point = Pt { x :: Integer, y :: Integer } deriving (Eq, Show)

これを GHCi にロードすると

Prelude> :l record.hs
Compiling Main             ( record.hs, interpreted )

record.hs:3:18:
    Multiple declarations of `Main.x'
    Declared at: record.hs:1:15
                 record.hs:3:18

record.hs:3:32:
    Multiple declarations of `Main.y'
    Declared at: record.hs:1:25
                 record.hs:3:32
Failed, modules loaded: none.

あー，やっぱりだめなわけね。

型シノニム（type synonym）とは，既存のデータ型に別名をつけるというもの。String が [Char] であるのがよい例。
型シノニムを宣言するには type 宣言を使う。

type String = [Char]

newtype 宣言は「新しい型」を宣言する。type 宣言と data 宣言の中間的なもので，実体は既存の型とおなじであっても，元の型とは違う扱いをしたい，という場合に使うらしい。たとえば「実体は整数だが負の値は取らない」みたいな。
でもこれ，具体的な宣言の仕方が書いてない。まあ，あまり使わないのかな。

cf. id:rubyco:20060531:pascal
cf. id:epics:20060530:1149000099

Ruby の Enumerable#inject は Haskell では foldl だ。
というわけで早速やってみよう。ただし，無限リストを扱えるように foldr をつかう。早くしないと 結城さんに先を越されちゃうぞ。

pascalTriangle = foldr (\n i -> [pascal n] ++ i) [[]] [1..]
  where pascal x | x == 1 = [1]
                 | otherwise = (\xs -> zipWith (+) (0:xs) (xs ++ [0])) (pascal (x-1))

結果。

*Main> putStr $ unlines $ map show $ take 10 $ pascalTriangle
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]

あー，でも，n 列目を作るのに再帰してるのが無駄っぽいなぁ。