何度も書いているのは、http://d.hatena.ne.jp/itchyny/20130209/1360417348を読んだから。 let rec foldr = T (fun _ (k : Thunk<Thunk<'a> -> Thunk<'b> -> 'b>) (z : Thunk<'b>) (list : Thunk<TList<'a>>) -> let rec go xs = match eval xs with | Nil -> z | Cons (y, ys) </tlist<'a></thunk<'a>…
コードは、「セクシー素数ベンチ(の非効率な実装)」を移植したもの。 open System.Linq let isPrime n = Enumerable.Range(2, n - 2) // {2..n-1} |> Seq.forall (fun i -> n % i <> 0) let sexyPrimes n = Enumerable.Range(9, n - 8) // {9..n} |> Seq.m…
type Thunk<'a> = T of (unit -> 'a) let eval (T x) = x () let apply f (x : Thunk<'a>) = T (fun _ -> (eval f) x) let one = T (fun _ -> 1) let two = T (fun _ -> 2) let add = T (fun _ x y -> eval x + eval y) let three = apply (apply add one) t…
Haskellで書いてもしょうがないのであとでF#にするか? 正格評価の言語だとunitがアウトだなきっと。最初から() -> a で渡してやらないと。 newtype Thunk a = T (() -> a) unit :: a -> Thunk a unit x = T (\y -> x) eval :: Thunk a -> a eval (T x) = x …
http://d.hatena.ne.jp/notogawa/20121201/1354389374 hoogleの使い方(型から引く)という技もそうだが、トップダウン思考が参考になった。
Applicativeの勉強のため、プログラミングHaskellのパーサーをApplicativeに変更してみた。 書いていると、ApplicativeというよりはAlternativeにするべきと分かったので、そのように実装した。 import Data.Char import Control.Applicative newtype Parser…
いろいろあるが、以下の3つかな。 値コンストラクタは型ではない たとえば、CircleとRectangleを含むShapeという独自のデータ型を定義するとする。Circleは半径を、Rectangleは幅と高さを持つとする。そういうデータ型はHaskellだとこんな感じで定義する。 d…
flip constとconst idが等価だってことは、Haskellになじんでくると素直に思い浮かんでくるものなのか? 命令型でいうと、forがwhileで書ける、みたいな感じで、プログラマの常識なのか? もしそうなら、まだぜんぜんHaskell脳になってないな、おれの頭。 や…
ファクンタ⇒アプリカティブ⇒モナドの順で力強くなってることを、リストを例に考えてみる。 ファンクタ1つのリストに対して、1引数の変換(map)ができる。 アプリカティブ複数のリストに対して直積をとって、多引数の変換ができる。 モナド変換だけじゃなく、…
window.twttr = (function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0], t = window.twttr || {}; if (d.getElementById(id)) return t; js = d.createElement(s); js.id = id; js.src = "https://platform.twitter.com/widgets.js"; fjs.paren…
16ヶ月もかけてしまったが、ついに全章の写経と練習問題を終えた! この先も本で学ぶとすれば、「すごいH」本か、もしくは「Real World Haskell」だろうか? でも、まずはrst76が紹介していた確率プログラミングかな。 例題だと、「雨が降る確率が0.3、その…
13.9 練習問題 以下の定義が与えられているとする。 map f [] = [] map f (x:xs) = f x : map f xs (f.g) x = f (g x) map f (map g xs) = map (f.g) xsであることを、xsに対する数学的帰納法で証明せよ。 xs = []の場合 左辺 = map f (map g []) = map f []…
とりあえず残りの問題だけ 13.9 練習問題 以下の定義が与えられているとする。 map f [] = [] map f (x:xs) = f x : map f xs (f.g) x = f (g x) map f (map g xs) = map (f.g) xsであることを、xsに対する数学的帰納法で証明せよ。 以下の定義が与えられて…
Stack Overflowに質問されていた、「In what areas might the use of F# be more appropriate than C#?」の回答を翻訳してみた。 simon cousinsの回答 私は、とあるエネルギー会社向けに、発電所のポートフォリオに関する国の発電スケジュールと取引ポジショ…
13.9 練習問題 付録Aにある標準ライブラリの中から重複のあるパターンを使って定義されている関数を探せ。 教科書を見ながら抜き出してみる。 ガードも重複パターンのうちかな? A.1 クラス min, max :: a -> a -> a min x y | x <= y = x | otherwise = y m…
13.9 練習問題 付録Aにある標準ライブラリの中から重複のあるパターンを使って定義されている関数を探せ。 いま手元に教科書がなくて、付録Aを確認できないので、今日はパス。 add n (Succ m) = Succ (add n m) であることをnに対する数学的帰納法で示せ。 n…
13.7 コンパイラーの正しさ 忙しかったのでかなり間が空いてしまった。 今回は10.5節で出てきた関数を、10.5節とは違った形で(コンパイルして実行することで)評価する関数を定義して、その関数の振る舞いがもとの関数の振る舞いと一致することを証明する。…
13.5 リストに対する数学的帰納法 リストも再帰的にオブジェクトが構築される型なので、数学的帰納法で論証できる。 reverse (reverse xs) = xsの証明。 xs = [] の場合 reverse (reverse []) = reverse [] = [] xs = ns のときに reverse (reverse xs) = xs…
ついに最終章! この最終章では、Haskellプログラミングを論証する方法を紹介する。まず等式推論の復習から始め、それがHaskellにどのように適用できるかを考える。そして、数学的帰納法という重要な技法を説明し、連結演算子を数学的帰納法に似た手法で除去…
12.9 練習問題 以下の式において、簡約可能式はどこか?また、選び出した簡約可能式が、最も内側か、 最も外側か、両方か、いずれでもないかを考えよ。 こんな感じ?簡約可能式に抜け漏れがなければいいけど。 1+(2*3) 2*3...最内 1+()...最外(追記)原著の…
問題文だけ転記。 12.9 練習問題 以下の式において、簡約可能式はどこか?また、選び出した簡約可能式が、最も内側か、 最も外側か、両方か、いずれでもないかを考えよ。 1+(2*3) (1+2)*(2+3) fst (1+2, 2+3) (λx→1+x) (2*3) 式 fst (1+2, 2+3) を評価する際…
12.5 無限のデータ構造 Haskellの遅延評価は、無限のデータ構造を相手にした時も、必要がない限り無限回の評価は行わない。 一般的に、遅延評価は次のような性質を持つ。すなわち、遅延評価を用いると、式が利用される文脈が要求する回数だけしか、その式は…
12.1 導入 一般的な命令型言語は、同じ式に対する評価順序が違うと結果が変わることがあるが、Haskellではどのような順序で評価しても(停止するのでない限り)同じ結果が得られる。 ぐぐってみたら、「チャーチ・ロッサー性」というのかな? 12.2 評価戦略 簡…
ってHaskellのdo記法なんだね。
11.7 練習問題 関数 choices、exprs、およびevalを用いて、1、3、7、10、25、50に対し可能な式は33,665,406個あり、そのうち4,672,540個のみが有効であることを確かめよ。 こんな感じでいいのかな。 もっと見た目よく関数合成したいんだけど。F#の |> みたい…
11.7 練習問題 ライブラリ関数concatとmapを用いる代わりに、リスト内包表記を使って、組み合わせの関数choicesを再定義せよ。 10章の練習問題でリストモナドについて書いたことを思い出せば簡単。 choices' :: [a] -> [[a]] choices' xs = [zs | ys <- subs…
昨日のHaskellコードをF#に移植してみた。 type Point = {X: int; Y: int;} static member ( + ) (p: Point, q: Point) = {X = p.X + q.X; Y = p.Y + q.Y;} static member ( - ) (p: Point, q: Point) = {X = p.X - q.X; Y = p.Y - q.Y;} type Pair = {Front…
10年ぐらい前の問題をHaskellで解いてみた。 問題は、「8×8ますの正方形のパネルを同じ形に2分割する分け方はいくつあるか」というもの。 ↓のコードは回転同型は考慮しているが鏡像同型は考慮してない。でもすっきりと書けたんじゃないかな。 (追記)Node型…
数日かけて写経したのでまとめて更新。 11.1 導入 切符番号遊びは、切符の端に書いてある四つの数字を使って、10になるように数式を組み立てる遊びである。 (中略)この章では、ゲームのルールを少し変更する。利用する数は任意の大きさで、全部を使わなく…