ラベル Haskell の投稿を表示しています。 すべての投稿を表示
ラベル Haskell の投稿を表示しています。 すべての投稿を表示

2010/04/10

再帰 継続 末尾

再帰なら継続渡しで書き直して末尾再帰にできるヨ!!
そんなことを耳にしていたんですが
どうも継続というものが良く分かっていません
まぁ、関数渡すらしいな、程度の認識

再帰といえば fold なわけですが
Haskell だと foldr、OCaml だと List.fold_right です
まぁ、何でもいいんですが
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
とか
let fold_right f lst init = match lst with
| [] -> init
| x::xs -> f x (fold_right f xs init)
とかそういうのです
要するに
fold [] = v
fold (x:xs) = f x (fold xs)
みたいなことになってればいいんです

で、これ末尾再帰にはなってないわけですよ
することに意味があるかは知らないんですよ
したいんですよ、末尾再帰に
できないんですよ、まだ継続とか関数渡すとかの理解浅いから

ぐぐりました
反復的プロセス、末尾再帰、継続渡しスタイル : torus solutions!
append が末尾再帰の刑に処せられていますがまぁ fold も同じようなもんです

fold f v [] k = k v
fold f v (x:xs) k = fold f v xs (\y -> k (f x y))

let rec fold f lst v k = match lst with
| [] -> k v
| (x::xs) -> fold f xs v (fun y -> k (f x y))
でもね、
continuation(継続)は末尾再帰の最適化手段ではない : メカAG
飽くまで「継続を使うと再帰が末尾再帰に直せる」というだけなので
このままでは「継続」の入口にも立っていないのでした

付録:

で fold には left もありましてこっちは最初から末尾再帰でしたが
(最近 Haskell ご無沙汰なので Haskell だけにしよう、もぉ面倒だ)
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
こんなだったか
これは例えば
foldl (+) 0 [1,2,3]
= (((0+1)+2)+3)
= (\k -> k.(+1)) ((\k -> k.(+2)) (+3)) 0
= (\x k -> k.(+x)) 1 ((\x k -> k.(+x)) 2 (+3)) 0
= (\x k -> (\y -> k (y+x))) 1 ((\x k -> (\y -> k (y+x))) 2 (\x k -> (\y -> (y+x))) 3 id) 0
= (foldr (\x k -> (\y -> k ((+) y x))) id [1,2,3]) 0
ははは、欺瞞にも程がある
でもまぁ
foldl f v lst = (foldr (\x k -> (\y -> k (f y x))) id lst) v
と書けないこともないということで
何が嬉しいのかは分かりません

2010/01/03

"doesdirectoryexist" socket

ディレクトリかどうか知りたいときってあります
$ ghci
Prelude> import System.Directory
Prelude System.Directory> doesDirectoryExist "/tmp/scim-panel-socket:0-foo"
True
Prelude System.Directory> getDirectoryContents "/tmp/scim-panel-socket:0-foo"
*** Exception: /tmp/scim-panel-socket:0-foo: getDirectoryContents: inappropriate type (Not a directory)
どないやねん

System.Directory を見てみると
s_isdir で判断してるらしいんだけどなぁ、よく分かんないなぁ
doesFileExist は doesDirectoryExist に not 取ってるみたいな感じ

でー、ググった、けど良く分からんかったけど Posix 思いだした
System.Posix.Files ってあった
Prelude> import System.Posix.Files
Prelude System.Posix.Files> status <- getFileStatus "/tmp/scim-panel-socket:0-foo"
Prelude System.Posix.Files> isDirectory status
False
Prelude System.Posix.Files> isNamedPipe status
False
Prelude System.Posix.Files> isSocket status
True
これかー

Windows とか良く知らないし
更に Posix な世界から出たことがあまり無い気がしてるんですが
あ、Windows のこととりあえず無視しておけばいいのか!!
や、System.Win32 ってのがあるのか...

2009/12/22

cabal-install ghc-6.12.1

GHC 6.12.1 が出たということで
IO と Unicode が仲良くなったとか噂を聴いて
インストールしてみようかなと思いました

でも、コンパイルする元気はないのでとりあえずバイナリーとってきます
http://haskell.org/ghc/dist/6.12.1/ghc-6.12.1-i386-unknown-linux-n.tar.bz2
を落としてインストールしてみました

で、cabal とか使いたいなと思ったんですが
Cabal は入ってるらしいんだけど cabal は入ってない!!
色々調べると cabal-install の 0.8 を入れるべきだそうで

あ、えっと、cabal ってのは python でいうと easy_install みたいな
Ruby でいうと gem みたいなやつです

cabal-install を入れるには network, HTTP, zlib を別途入れないとで
network が parsec を、HTTP が parsec と mtl を
更に parsec が mtl を要求しているので
mtl -> parsec -> network -> HTTP -> zlib
の順でインストールしました

で、「よーし HsOpenSSL 入れちゃうぞー」と思ったら
$ cabal install HsOpenSSL
Resolving dependencies...
cabal: cannot configure HsOpenSSL-0.6.5. It requires integer -any
There is no available version of integer that satisfies -any
あらら

2009/12/03

Haskell import AF_INET

不要なものを import するなんて!
ってのが何原理主義なんだか分からないですが
fromMaybe だけ使いたい! って思ったら
import Data.Maybe (fromMaybe)
ってしろって色々書いてあります
素敵

AF_INET が欲しいと思ったんで
import Network.Socket (AF_INET)
ってしてみました
$ ghci af_inet.hs
GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( af_inet.hs, interpreted )

af_inet.hs:1:23: Module `Network.Socket' does not export `AF_INET'
Failed, modules loaded: none.
あら、"does not export" って言われてしまった

Prelude Network.Socket> :i AF_INET
data Family = ... | AF_INET | ...
-- Defined in Network.Socket.Internal
なるほど
AF_INET は Family っていう型の data constructor らしい
だから素直には呼べないのかな?
import Network.Socket (Family)
これは通るんだけど
$ ghci af_inet.hs
GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( af_inet.hs, interpreted )
Ok, modules loaded: Main.
*Main> AF_INET

<interactive>:1:0: Not in scope: data constructor `AF_INET'
そうよね、うんうん

残念ながらプログラミング Haskell にも記述が無く
色々ググっていたんですが、結局どうすればいいかっていうと
import Network.Socket (Family(AF_INET))
こうすればいいみたいでした
どこでこの記述見つけたんだかもぉ忘れちゃった

原理主義疲れる

haskell timeout

プログラミング Haskell って素敵本も買ってみて、
ちょいちょい「お勉強」してるんですが
Haskell で timeout したくなったらどうしよう!?
心配性なので事前に調べておかないと気になって仕方がありません
ググってみました

System.Timeout
timeout :: Int -> IO a -> IO (Maybe a)
何マイクロ秒待つか指定して
IO しようとして、失敗すると Nothing 返ってくるっぽい

試してみた
Prelude Network.HTTP System.Timeout> timeout (3*10^6) $ simpleHTTP $ getRequest "http://10.0.0.1/"
Nothing
Prelude Network.HTTP System.Timeout> timeout (3*10^6) $ simpleHTTP $ getRequest "http://google.com/"
Just (Right HTTP/1.1 301 Moved Permanently
Location: http://www.google.com/
Content-Type: text/html; charset=UTF-8
Date: Sat, 05 Dec 2009 04:49:50 GMT
Expires: Mon, 04 Jan 2010 04:49:50 GMT
Cache-Control: public, max-age=2592000
Server: gws
Content-Length: 219
X-XSS-Protection: 0
Connection: close

)
Prelude Network.HTTP System.Timeout>
何だこの最後の )Just ( の pair の ) じゃ
でもまぁ、待ててるみたいでした
Network.HTTP に timeout がある気がしないでもないけど、いつか調べよう

2009/11/21

openssl haskell context

Haskell で Socket 使って少し通信できるようになったので
SSL で通信でもしてやろうかと思いました
クライアントとして
引きつづき HsOpenSSL を使って

OpenSSL でクライアントとして接続というと
context っていうクライアント認証の情報とか SSL のバージョンとかと
あと socket を作っておいて
その二つを合わせて SSL の接続へと socket を昇格? させます

で、ググりゃそりゃリファレンスが出てくるので
OpenSSL.Session
ghci で上に従ってやってみようと思ったんですが何か上手くいかず
色々ググったりして散々悩んでみたんですが
コード書いてコンパイルしたら通ってしまいました
ghci だとダメってよりは、withOpenSSL が無くてダメだったのかな

折角なんで Firefox から ThawtePremiumServerCA って証明書を抜き
引き数に hostname を取って 443 port で SSL 通信して
サーバ証明書を取ってきて証明書の検証ができるかどうか試してみました
$ ./cert_check www.google.com
VerifyFailure
$ ./cert_check www.blogger.com
VerifySuccess
有効期限の確認も FQDN と CN の比較もしてなくて
ルート証明書の公開鍵でサーバ証明書の署名の確認してるだけですが

import System
import Data.Maybe
import Network.Socket
import Network.BSD
import OpenSSL
import OpenSSL.Session
import OpenSSL.X509
import OpenSSL.PEM
import OpenSSL.RSA
import OpenSSL.EVP.PKey

main = withOpenSSL $
do
(host:_) <- getArgs
addr <- return . head . hostAddresses =<< getHostByName host

ctx <- context
sock <- socket AF_INET Stream 0
Network.Socket.connect sock (SockAddrInet 443 addr)
ssl <- connection ctx sock
OpenSSL.Session.connect ssl
x509 <- return . fromJust =<< getPeerCertificate ssl
-- putStr =<< writeX509 x509
OpenSSL.Session.shutdown ssl Unidirectional

root <- readX509 =<< readFile "ThawtePremiumServerCA.crt"
pk <- return . fromJust . toRSAKey =<< getPublicKey root
putStrLn . show =<< verifyX509 x509 pk
where
toRSAKey :: SomePublicKey -> Maybe RSAPubKey
toRSAKey = toPublicKey

2009/11/20

haskell hostname resolve

続きまして、HTTP でも叩こうかと思いました
直に Network.Socket を叩くよ!!

ってまぁ、流石にそんなことしてる人は沢山いらっしゃいまして
いくらでもサンプルが出てくるんですがシンプルだったのは
関数型プログラミング言語Haskell Part6
2ちゃんねるの過去ログの 607 さんでした
ちなみに検索語は "import Network.Socket"

で、挙がってた sample は
import Network.Socket 
main = putStrLn =<< do
sock <- socket AF_INET Stream 0
addr <- inet_addr "66.249.89.104" >>= \x -> return $ SockAddrInet 80 x
connect sock addr
send sock "GET / HTTP/1.1\nHost: www.google.co.jp\n\n"
recv sock 10000000 >>= \x -> sClose sock >> return x
おぉぉ

IP address ってのはちょっと寂しかったので
名前を解決してやりたいなと思いもうちょっとググりました
Network.BSD
なるほど、getHostByName 使えと
上の2ちゃんのログの 604 さんが
インタフェースはCのAPIそのままだから、そっちを調べるべき。
っつってたので
C のこと分かってればいいみたいです
わたし? えぇ、分かってないですけど

> :t getHostByName
getHostByName :: HostName -> IO HostEntry
> :i HostEntry
data HostEntry
= HostEntry {hostName :: HostName,
hostAliases :: [HostName],
hostFamily :: Network.Socket.Internal.Family,
hostAddresses :: [Network.Socket.Internal.HostAddress]}
-- Defined in Network.BSD
あと、HostName は String のこと
HostEntry の中の hostAddresses に IP address が入ってるので
> getHostByName "www.google.com" >>= return . hostAddresses
[1750726978,1666840898,2472147266,1733949762]
10進でアドレス見せてくれます

つわけで、こんなん作ったら
import System
import Network.BSD
import Network.Socket

main = do (host:path:_) <- getArgs
addr <- return . head . hostAddresses =<< getHostByName host
sock <- socket AF_INET Stream 0
connect sock (SockAddrInet 80 addr)
send sock $ "GET " ++ path ++ " HTTP/1.1\nHost: " ++ host ++ "\n\n"
putStrLn =<< recv sock 100000
sClose sock
こんなん出ました
$ ./get www.ietf.org /rfc/rfc5280.txt
HTTP/1.1 200 OK
Date: Fri, 20 Nov 2009 08:10:29 GMT
Server: Apache/2.2.4 (Linux/SUSE) mod_ssl/2.2.4 OpenSSL/0.9.8e PHP/5.2.6 with Suhosin-Patch mod_python/3.3.1 Python/2.5.1 mod_perl/2.0.3 Perl/v5.8.8
Last-Modified: Wed, 07 May 2008 17:42:25 GMT
ETag: "1caf1b6-56144-7cddc240"
Accept-Ranges: bytes
Content-Length: 352580
Vary: Accept-Encoding
Content-Type: text/plain







Network Working Group D. Cooper
Request for Comments: 5280 NIST
Obsoletes: 3280, 4325, 4630 S. Santesson
Category: Standards Track Microsoft
S. Farrell
Trinity College Dublin
S. Boeyen
Entrust
R. Housley
Vigil Security
W. Polk
NIST
May 2008


Internet X.509 Public Key Infrastructure
なんでこれ途中で切れるの?
recv に渡す数字でちゃんと表示内容変化してるのに
気付いていなかったみたいです
socket が分かっていない...

"Couldn't match expected type `IO *' against inferred type"

Haskell がきれいらしいので Haskell 少し真面目にしようかなと
証明書くらい読めなきゃいけないだろうということで X.509 を読むことに

ググったら HsOpenSSL という OpenSSL の binding があり
cabal は入れてあったので
$ cabal install HsOpenSSL
でインストール終了
OpenSSL を見て
    main = withOpenSSL $
do ...
と withOpenSSL で囲むというのと
Learning After School » HsOpenSSL Update を見て
ghci には --make というオプションを与えないとダメなことを認識

とりあえず読めればいいと思ったので
PEM への PATH を最初の引数で取ってそれを解釈して吐くことにしました
HsOpenSSL 関係で使った関数は
OpenSSL.PEM.readX509 :: String -> IO X509
OpenSSL.X509.getVersion :: X509 -> IO Int
OpenSSL.X509.getVersiongetSerialNumber :: X509 -> IO Integer
OpenSSL.X509.getVersiongetNotBefore :: X509 -> IO UTCTime
OpenSSL.X509.getVersiongetNotAfter :: X509 -> IO UTCTime
OpenSSL.X509.getVersiongetIssuerName :: X509 -> Bool -> IO [(String, String)]
OpenSSL.X509.getVersiongetSubjectName :: X509 -> Bool -> IO [(String, String)]
OpenSSL.X509.getVersiongetPublicKey :: X509 -> IO SomePublicKey
OpenSSL.EVP.PKey.toPublicKey :: (PublicKey k) => SomePublicKey -> Maybe k

UTCTime ってのは Data.Time.Clock で定義されてるんだけど
Show のインスタンスなので show で文字列にできる
getIssuerName と getSubjectName の取る Bool は名前の省略するか否か
tuple は ("countryName", "JP") みたいなのが入ってる

でー、ここまでは良かったんだけど分からなかったのが公開鍵で
SomePublicKey ってのは class なんだけど
> :i SomePublicKey
data SomePublicKey where
OpenSSL.EVP.PKey.SomePublicKey :: forall k.
(PublicKey k) =>
!k -> SomePublicKey
-- Defined in OpenSSL.EVP.PKey
instance Eq SomePublicKey -- Defined in OpenSSL.EVP.PKey
instance PublicKey SomePublicKey -- Defined in OpenSSL.EVP.PKey
instance PKey SomePublicKey -- Defined in OpenSSL.EVP.PKey
> :i PublicKey
class (Eq k, Data.Typeable.Typeable k, PKey k) => PublicKey k where
fromPublicKey :: k -> SomePublicKey
toPublicKey :: SomePublicKey -> Maybe k
-- Defined in OpenSSL.EVP.PKey
instance PublicKey RSAKeyPair -- Defined in OpenSSL.EVP.PKey
instance PublicKey SomePublicKey -- Defined in OpenSSL.EVP.PKey
instance PublicKey SomeKeyPair -- Defined in OpenSSL.EVP.PKey
instance PublicKey RSAPubKey -- Defined in OpenSSL.EVP.PKey

type とか class に関する理解が不足しているのは分かりつつ
toPublicKey に SomePublicKey かましたらいいんでしょ? と思って
で、IO SomePublicKey だから bind とか使ったらいいんでしょ? と思って
pk <- getPublicKey x509 >>= toPublicKey
としてみたら
Couldn't match expected type `IO b' against inferred type `Maybe k'
と言われてしまい
これが解決できなくて検索しました

Re: [Haskell-cafe] Convert IO Int to Int: msg#00458 haskell-cafe@haskell.org
何となく分かったのは、IO の中身取り出そうとしてて、そりゃダメだ
return かましてらしたんで、かましてみたら IO で包めて通りました!
と思いきや
SomePublicKey ってののインスタンスも指定しないとダメみたいで
:: Maybe RSAPublicKey ってのを付けないと toPubicKey が上手く動かず
ん〜、理解不足、RSA 決め打ち気持ち悪い

でもまぁ、こんな感じでとりあえず中身見れるようになりました
module Main where
import System
import OpenSSL
import OpenSSL.PEM
import OpenSSL.X509
import OpenSSL.EVP.PKey
import OpenSSL.RSA
import Data.Maybe

main :: IO ()
main = withOpenSSL $
do
x509 <- OpenSSL.PEM.readX509 =<< head =<< getArgs
putStr "version: "
getVersion x509 >>= putStrLn . show . succ
putStr "serialNumber: "
getSerialNumber x509 >>= putStrLn . show
putStr "notBefore: "
getNotBefore x509 >>= putStrLn . show
putStr "notAfter: "
getNotAfter x509 >>= putStrLn . show

putStrLn ""
issuerRDNs <- getIssuerName x509 True
putStrLn "[issuer]"
mapM_ printRDN issuerRDNs
subjectRDNs <- getSubjectName x509 True
putStrLn "[subject]"
mapM_ printRDN subjectRDNs

putStrLn "[publickKey]"
somePublicKey <- getPublicKey x509
pk <- return $ fromJust (toPublicKey somePublicKey :: Maybe RSAPubKey)
putStr "e = "
putStrLn $ show $ rsaE pk
putStr "n = "
putStrLn $ show $ rsaN pk<
where
printRDN (f, s) = putStrLn (f ++ " = " ++ s)
とりあえず動いたんで満足しました

$ ./x509 www.blogger.com.crt 
version: 3
serialNumber: 154451598012349719216436864807249350442
notBefore: 2008-04-29 22:42:19 UTC
notAfter: 2010-05-26 11:11:00 UTC

[issuer]
countryName = ZA
stateOrProvinceName = Western Cape
localityName = Cape Town
organizationName = Thawte Consulting cc
organizationalUnitName = Certification Services Division
commonName = Thawte Premium Server CA
emailAddress = premium-server@thawte.com
[subject]
countryName = US
stateOrProvinceName = California
localityName = Mountain View
organizationName = Google Inc
commonName = *.blogger.com
[publickKey]
e = 65537
n = 156261988165875299258992916522864140599934684523601467326503718745802091107083682835929499666111345772555979343409161090600093388197459190695135388517589095274179717212596199311728073635629373769115406240413244621434604136126497937524426697977932393973863819806782187408995863143657362345664311920806817108659

2009/03/29

Kleisli

いつまでも Haskell とかのこと調べてても仕方ないんですが
コード書かないと
でも何だか楽しいのでバックグラウンドのことばかり調べていました

だって、副作用を避けつつ IO する仕組みが分かればいいわけですよ
別に monad が何だとか Kleisli が誰だとかどうでもいいわけですよ
でもまぁ、調べちゃったと

とか

読んだら楽しいのかなと思ってるんですが最終的には

なのかなぁ

でも、Arrow ってのもあるらしい (ぽわわわ〜ん)

2009/03/23

ghci readline

Haskell の記事を少しずつ読んでいるんですが
ばりばりライブラリを追加するようになってきたようで
Debian 環境にそういうライブラリを入れるのは何だか気持ち悪いし
コンパイルくらいしないとダメだろうと思ったので wget して configure して make

GHC は GHC が無いとダメらしいので一旦 uninstall してみた GHC を再度インストールしたりする

で〜、GHCi を起動してみたら Ctrl-P とかが効かない!!
とても慌てて readline とかが入ってないかどうか調べると入っている
う〜んと思って ghci readline で検索したら
GHC 6.10.1 で readlineから editlineに変わっていたらしい

そーかー、ということで editline 入れて configure し直して make してるところ
こんどは動くといいなぁ

追記
ダメだったー、GHC 作るのに使う GHC が editline ready でないといけないらしい
フガー!!

追記2 (2009/11/16)
GHC 6.10.3 と C-p
設定ファイルで設定すれば良かったみたい
無念

2009/03/21

spaces haskell

SoftwareDesign の 4 月号に Haskell の入門が書かれています
Software Design 2009年 04月号 <- これ
関数型への憧れ? もあるので読んでみているんだけど誤植が大目かも

P.137 の
combine n l = rjust 6 ++ ": " ++ l

は多分
combine n l = rjust 6 (show n) ++ ": " ++ l

の間違い

本文中に
show n は整数を文字列に変換

とヒントが書かれてたから分かったので良かったです

「spaces haskell」とか「take haskell」とか検索したら Haskell のリファレンスが出てきて
ちゃんとリファレンス読んで理解もできたので理解が進んで良かった

でもなー、Haskell で何作れるんだろうなぁ、みな何作ってるんだろうなぁ
ふつうのHaskell買っちゃおうかなぁ