01122009 Haskell

foldrでfilter

RWHのp.99

右から畳み込むはずなのに、、、不思議な感じがする。

myfilter p xs = foldr step [] xs
                where step x ys | p x = x:ys
                                | otherwise = ys

myfilter odd [1,2,3,4,5,6]
[1,3,5]

結局これは

(1:(3:(5:[])))

を評価してんのか。

ProductName Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan
オライリージャパン / 3990円 ( 2009-10-26 )


27112009 Haskell

プログラミングHaskell8章(関数型パーサー)

プログラミングHaskell8章

ProductName プログラミングHaskell
Graham Hutton
オーム社 / 2940円 ( 2009-11-11 )


本の通りにdo記法使うと動かなかったのでbindをつかってせっせと書いた。そのおかげで、←とか>>=見るとラムダ式が意識できるようになってきた。

第14回 関数脳のつくり方　Second Season　〜モナドで悟りをひらく〜

関数型言語で「プログラムの実行順序を保証」したり

import Char
type Parser a = String -> [(a,String)]

myreturn :: a -> Parser a
myreturn v = \inp -> [(v,inp)]

myfailure :: Parser a
myfailure = \inp -> []

myitem :: Parser Char
myitem = \inp -> case inp of 
                 [] -> []
                 (x:xs) -> [(x,xs)]

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

(>>==) :: Parser a -> (a -> Parser b) -> Parser b
p >>== f = \inp -> case parse p inp of
                    [] -> []
                    [(v,out)] -> parse (f v) out

-- p :: Parser (Char,Char)
-- p = myitem >>== \x -> 
--     myitem >>== \y -> 
--     myitem >>== \z -> 
--     myreturn (x,z)

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case parse p inp of
                    [] -> parse q inp
                    [(v,out)] -> [(v,out)]
sat :: (Char -> Bool) -> Parser Char
sat p = myitem >>== \x -> if p x then myreturn x else myfailure

digit :: Parser Char
digit = sat isDigit

lower :: Parser Char
lower = sat isLower

upper :: Parser Char
upper = sat isUpper

letter :: Parser Char
letter = sat isAlpha

alphanum :: Parser Char
alphanum = sat isAlphaNum

char :: Char -> Parser Char
char x = sat (== x)

string :: String -> Parser String
string [] = myreturn []
string (x:xs) = char x >>== \_ -> string xs >>== \_ -> myreturn (x:xs)

many :: Parser a -> Parser [a]
many p = many1 p +++ myreturn []
many1 :: Parser a -> Parser [a]
many1 p = p >>== \v -> many p >>== \vs -> myreturn (v:vs)

ident :: Parser String
ident = lower >>== \x -> many alphanum >>== \xs -> myreturn (x:xs)

nat :: Parser Int
nat = many1 digit >>== \xs -> myreturn (read xs)

space :: Parser ()
space = many (sat isSpace) >>== \_ -> myreturn ()

token :: Parser a -> Parser a
token p = space >>== \_ -> p >>== \v -> space >>== \_ -> myreturn v

identifer :: Parser String
identifer = token ident

natural :: Parser Int
natural = token nat

symbol :: String -> Parser String
symbol xs = token (string xs)

-- 8-1 --
int :: Parser Int
int = char '-' >>== \_ -> nat >>== \n -> myreturn (-n) +++ nat
-- --  --

-- 8-2 --
comment :: Parser ()
comment = string "--" >>== \_ -> many (sat (/= '\n')) >>== \_ -> myreturn ()
-- --  --

22112009 Haskell Emacs

Haskellモードにフック追加

->と<-を割り当てといた。

(add-hook 'haskell-mode-hook '(lambda ()
(local-set-key "\C-j" (lambda () (interactive)(insert "->")))
(local-set-key "\M-j" (lambda ()(interactive)(insert "<-")))
))

19112009 Haskell

「プログラミングHaskell」読んだ

これはかなりナイスな本です。あんま細かいところに陥らずに関数型プログラミングの思考みたいなものが学べるようになってる。

ProductName プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
通常3～6週間以内に発送

モナドに関しても、「モナドとは？」から入るわけではなくて、8章のパーサー、9章の対話型プログラム、そして10章の型に至る過程で自然に出てくる。

個人的には4,5章の関数とリスト内包のとこと8-11章が面白かった。逆に最終章の13章はちょっとよくわからなかった。

  • 相互再帰(Ocamlでやった)
  • dataによる型宣言では構成子が引数をとることができる
  • 構成子関数は評価済みであり、それ以上簡約できない
  • モナドという概念は一般化された型
  • 最内簡約と最外簡約はそれぞれ値渡しと名前渡し
  • 遅延評価とはポインタによる共有を用いた名前渡し

特に最後の二つは、新鮮だった。

あとは暇をみつけて問題解いてく

18112009 Haskell

Haskellの関数合成

ご近所haskellerのringtaroさんがつぶやいてたので。

Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
Prelude> :t ($)
($) :: (a -> b) -> a -> b

(.)はb->cとa->bっていう関数を受け取ってa->cという関数を返す。だから関数合成

Prelude> :t head
head :: [a] -> a
Prelude> :t (drop 1)
(drop 1) :: [a] -> [a]
Prelude> :t head . (drop 1)
head . (drop 1) :: [a] -> a

($)は dropを評価した結果のリストをheadにわたすだけ。なので、下の書き方はだめ。

Prelude> :t ($) head (drop 1)

<interactive>:1:10:
    Couldn't match expected type `[a]'
           against inferred type `[a1] -> [a1]'
    In the second argument of `($)', namely `(drop 1)'
    In the expression: ($) head (drop 1)

括弧省略の記法なのに括弧入れまくり

Prelude> :t ($) head ((drop 1) [1,2,3])
($) head ((drop 1) [1,2,3]) :: (Num a) => a

ProductName プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
通常3～6週間以内に発送

16112009 Haskell Python

リスト内包表記で素数チェック

プログラミングHaskell読みはじめた。この本はHaskellプログラミングの入門書というよりは、Haskellプログラミングとはどういう考え方で書いていくかの入門書的な感じがする。いきなりこれ読んでもhaskellでコード書けないんじゃないだろうか。

4章のリスト内包表記の章で、ある数の因数を求める関数を定義して、それを用いて素数判定をしていたのでpythonでもやってみた。

def factors(n):
  return [x for x in range(1,n+1) if n % x == 0]

def is_prime(n):
  return True if len(factors(n)) == 2 else False

あとHaskellだと

[x|x <- xs | xs <- a]

でconcatenateできて便利なんでこれもpythonで、とか思ったんだけど

リストの要素が常にひとつのときのみ

a = [[1], [2], [3]]
[x for [x] in a] # [1, 2, 3]

ってやればできるんだけど、二つ以上の要素になった場合が分からんかった。

ProductName プログラミングHaskell
Graham Hutton
オーム社 / 2940円 ( 2009-11-11 )


この本ほとんど疑似コード(?)なので考えるにはよいですな。お薦め。

03012007 Haskell

ポイントフリースタイルのhead

普通のhaskellプログラミングの216ページに

ポイントフリースタイルへの書き換えは脊髄反射の速度でできるようにしてください。

と書いてあったのだけど、脊髄どころか反射すらできない。

firstNLines :: Int -> String - String
firstNLines n = unlines . take n . lines

nを押し出すのってどうやるんだろうか?

追記07.01.03

解決したヨ。

03012007 Haskell

ポイントフリーなhead.hs

下の式を完全なポイントフリースタイルにする方法を色々と考えてみたんだけど。

firstNLines n = unlines . take n . lines

結局分からんかったので、mixiで聞いてみたらさくっと教えてもらえた（ありがたい）。

unlines . take n . lines
(unlines . take n) . lines
(. lines) (unlines . take n)
(. lines) ((unlines .) (take n))
((. lines) . (unlines .)) (take n)
((. lines) . (unlines .)) . take
(. lines) . (unlines .) . take

.って演算子として考えればよいらしい。だから、左側を取るように書き換えてやればいいのか。

Prelude> 5 + 7
12
Prelude> (+ 7) 5
12

(+)だとこんな感じ。

型を確認すると

Prelude> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

.は(b -> c)と(a -> b)という関数をとってa->cという関数を合成する関数(二項演算子?)なのか。

(.) :: (b -> c) -> (a -> b) -> (a -> c)

関数合成で、変数が消えていくのは、こういうことなのね。

25092006 Haskell

相変わらずモナドが

モナドで躓いて以来、ちょっとご無沙汰していたhaskellだが、ちょっとまとまった時間ができたので、この週末でじっくり考えてみた。

モナドだけに、読むたび必ず睡魔に襲われる（参照透明性確保！）でも理解度はちょっぴり向上してるっぽい(つまり副作用)。

檜山正幸のキマイラ飼育記はjavascriptを例にして、純関数にすること（参照透明性の確保?）と型を揃えることが重要っぽいあたりが理解できた。
で、HaHaHa!では思考をもうチョイ広げて、とりまく環境の変化ということに思いをめぐらせればいいということを理解した。特に図がわかりやすくて、かなり理解が進んだと思う。
で、それから、実際にperlの例を見るとを～とか思う。

変数の代入をIOと考えればtieって参照透明性を確保しつつ、副作用を発生させることができるのね。この場合にいわゆるモナド則は成り立つのかなと考えてみたけど、なんとなく成り立つのかなと思ったり。

と、ここらへんまで理解した気になって、再度ふつうのhaskellを。

ProductName ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門
青木 峰郎
ソフトバンククリエイティブ / ?円 ( 2006-06-01 )


なんとなくわかってキテルっぽいが、じゃぁ、MaybeモナドとかListモナドって何なのヨっていうか、モナドって一体何さ?っていうあたりがわからなくなってきた。さらにperlのtieなんかで実装できるってことは、モナド則っていうのは結局なんなのってのがよくわからん。

ふつうのhaskellに
モナドを定義の観点からみるならばモナド則がすべて
とあるように、モナド則を感覚で理解しなければならんのかな。

All About Monads

ほんとうにモナドを理解するには、モナドを使ったコードを経験することが最良 の方法です。

というわけで、コードを書こう。

19082006 Haskell

haskellだとフィボナッチ数列を表現すればいいのか

コメントでhaskellでフィボナッチの別解をもらったが、パッと見てもなぜこれでフィボナッチ数列ができるのかいまいちわからんかったので、よく読んでみたヨ。

まずは型チェック。 見ればわかるとおりfibはリストを返す関数ですな。つまり、fibを実行するとフィボナッチ数がどんどこどんどことそれこそとめどなく溢れてくる(はず)

fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)

これを　fib.hsという名前で保存してghciで実行してみる。

$ghci
*Main> :l fib.hs
*Main> fib

をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。ちなみにlengthでリストの長さをはかってみると、プロンプトがかえってこないゾ。さすが無限リスト。

zipWithの型とtailの型はこんな感じ。

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> :t tail
tail :: [a] -> [a]

zipWithは高階関数で、+関数をfibとtail fibに適用して新しいリストをつくるわけですな。tailは先頭の要素を取り除いたリストを返す関数だから、、、うーんやってることはわかるんだけど、イマイチイメージできん。

と悩んでたら、Wikipediaに書き下されてる表をみつけて納得した。perlで同じことやろうとするとまず有限個の要素をもつ配列があってみたいなところから始まるから、こういう表現はできないな。というわけで、目からうろこっていうか、ちょっと感動した。

ここで考えたようなn-1番目とn番目のフィボナッチ数が与えられたときにn+1番目のフィボナッチ数を求めるということを考えるのではなくて、そもそもフィボナッチ数列とは何かを考えて、それを無限リストとして表現することを考えればよいんですよと。

となると、リスト内包表記も感動するような綺麗さダ。

fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]

Haskell - Wikipedia

GHCの並列リスト内包表記(GHCの拡張は特別なコマンドラインフラグによって有効にしなければならない。

とあるのが、なにが問題なんだかわからんので、とりあえず実行してやろう。

fib4.hs:1:15: Illegal parallel list comprehension: use -fglasgow-exts
Failed, modules loaded: none.

デフォルトだと、同じリストが複数でてくるような表記の仕方(この場合はfibs)は問題あるということなのかな

ghci -fglasgow-exts

とオプションを指定して実行することで、OK。をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。

haskell素敵過ぎ