Hatena’s Kitchen

Haskell勉強会 #1

Haskell | 01:12 |

誠に恐縮なのですが、チームリーダがチャンスをくれたので、社内でHaskell勉強会なるものをやらせていただきました。

人に教えるのは、苦手分野だと自覚しつつも特攻し、見事撃沈しました。参加者のみなさま期待に添えず申し訳ありませんでした。

結局人に教えることができないということは、自分が理解していないということなので、まだまだ勉強不足ということを実感しました。

と、反省ばかり残る勉強会だったわけですが、bonarさんが興味をしめしてくださったので、僕なりの書き方を紹介しようと思います。

お題は、ウラムの問題（3n+1問題）です。（恥ずかしながらこういう問題があることすら知りませんでした。。。）

ulam :: Integer -> [Integer]
ulam 1 = 1:[]
ulam n | even n = n:(ulam $ n `div` 2)
ulam n = n:(ulam $ n * 3 + 1)

bonarさんは、Debug.Traceを駆使して、収束の過程をのぞいていますが、そもそも数列全体を俯瞰したいのであれば、数列を返す関数にしてしまうのがてっとり早いと思います。と、いうわけで上のコードになりました。コードの本質は、bonarさんが書かれているものと変わらないので、重箱のすみをつつくような指摘で恐縮です。。

これを実行してみると

tom-macbook ~ $ ghci ulam.hs
GHCi, version 6.10.2: 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             ( ulam.hs, interpreted )
Ok, modules loaded: Main.
*Main> ulam 6
[6,3,10,5,16,8,4,2,1]

と、1に収束していく様子を見ることができます。

僕は頭が悪いので、良い証明は思いつかないのですが、以下のコードを無限に走らせつづければ、いつか反例が見つかるかもしれません。

Main> filter (/=1) $  map (last . ulam) [1..]

本当は、この例でQuickCheckとかを使ったテストを紹介したかったのですが、諸事情によりほろ酔い状態なので、

まじめな話は次回書くことにします。

Shibuya.lisp#2 に行ってきました。

12:06 |

http://shibuya.lisp-users.org/2009/02/28/sltt-2-tb/

なんていうか出演陣が豪華すぎて、タダで見ちゃっていいのかと不安になる感じ。

運営者の皆様、出演者の皆様、ありがとうございました。

印象に残ったものを書き残しておきます。

• scheme処理系を書くなら、3impというのを読むといいらしい。
  • 日本語の情報源 → http://mono.kmc.gr.jp/~yhara/w/?Reading3imp.pdf
• 'Evalquoted in simple fortran'
  • タダでは読めないかも。。？ → http://www.springerlink.com/content/g653169260k53444/
• 'Think recursively write functionally'
• Cyan
  • 非S式のマクロ。おもしろそう。
• lazyS
  • なんのために遅延評価するのか。
• 平行四辺形

とくに考えさせられたこと。

• PerlとかRubyとか言語仕様がないインタプリタ言語は。。。
• schemeはLispではない
  • 名前空間を統一したせいでいろいろ無理が生じている
• Common Lispは速い。
• 遅い言語はやっぱりダメだ。
• 言語とライブラリーの仕様わけても、結局ライブラリの仕様が膨大になるなら意味ない
• 委員会言語
• 趣味でLispやってますとか聞きたくない
• Lisp使いたいと言って、上司に止められたぐらいであきらめるぐらいのモチベーションならLisp使わなくていい。

やっぱり仕事で使わないとだめか。

自分の無力さとぬるさに気づかされる一日でした。

となりにshelarcyさんが座っておられたのだけど、おそれおおくて(というかビビって)はなしかけられなかった。

Haskellのdata宣言の"!"マーク

Haskell | 00:09 |

Real World Haskellのp.417ぐらいで、いきなり

data Regex = Regex !(ForeignPtr PCRE) !ByteString deriving (Eq, Ord, Show)

みたいなコードが出てきて、この"!"はなんぞと思って調べたのでメモ。

ひょっとしたら、p.417までのどこかで説明されているのかも知らないけど全然頭に残ってなかった。

結論としては、

"!"がついてるフィールドは正格評価(strict evaluation)

になるらしい。

data Foo = Foo !Int deriving Show

main = let f = Foo (1 `div` 0) in f `seq` print "OK"

このコードの"Foo !Int"の部分の"!"があるとruntime errorになるけど、"!"をはずすと何も起こらない。

なるほど。

HaskellのFFIはとっても簡単

Haskell | 23:19 |

Real World Haskellの読書メモが停滞していますが、読む方は地道に進んでいます。

今17章のFFIのところ。

FFIとは、Foreign Function Interfaceの略で、Haskellプログラムの中で他の言語の関数を読んだり、その逆をしたりといった話。

本の中では、HaskellからCの関数を呼ぶ話がメインです。

一読しかしてなくて、まだわかっていないところも多くあるのだけれど、例えばCで書いたHello WorldをHaskellから呼び出すのはとっても簡単です。

用意するファイルは3つ。

hello.h

#ifndef HELLO_H
#define HELLO_H
#include <stdio.h>

void hello(void);

#endif /* HELLO_H */

hello.c

#include "hello.h"

void hello(void)
{
    printf("Hello World!\n");
}

Hello.hs

{-# LANGUAGE ForeignFunctionInterface #-}

import Foreign

foreign import ccall "hello.h hello" c_hello :: IO ()

要点は、foreign import 〜というところ。

hello.hというヘッダにある、helloという関数を Haskellの世界で、 c_hello :: IO ()というアクションとして使いますよ。という感じのことを宣言しています。

hello関数は、副作用を起こして、何も返さないので、haskellの世界での型はIO () となるわけです。

使い方も簡単。

$ gcc -c hello.c
$ ghci Hello.hs hello.o
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Loading object (static) hello.o ... done
final link ... done
[1 of 1] Compiling Main             ( Hello.hs, interpreted )
Ok, modules loaded: Main.
*Main> c_hello
Hello World!
*Main> 

感動すら覚える簡単さ。PerlでXSを覚えるよりもはるかにラクですね。

Cの関数は引数が多くなったり、呼び出す順序に暗黙の制約があったりしますが、Haskellでbindingを書いてやることで、直感的に使いやすいインターフェースに改良することができます。

てなところが大きな強みだなぁと思っています。

HaskellのContモナドに触れてみる

Haskell | 19:34 |

Real World Haskellの消化速度が落ちてきたので、息抜きにContモナド(=継続)の解説を読んでみる。

(たぶん、RWH本編には、Contモナドは出てこない。)

"Continuation モナドの濫用は理解や保守が不可能なコードをつくり出す 可能性があります．"と書いてあるけど、とりあえず読む。

定義

 newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } -- r は計算全体の最終の型
  
instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a                       -- i.e. return a = \k -> k a 
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) -- i.e. c >>= f = \k -> c (\a -> f a k) 

Haskellの継続は、Monadの形にまとめられている。

コメントにもある通り、Cont r aという型は、途中の計算の型がaで、最終的にはrの値を返すような計算を表している。

Cont型がラップしているデータの型を見る

runCont :: ((a -> r) -> r)

最初の(a -> r) = gと置き換えると 、(g -> r)という形をしているので、Contがラップしているのは、1引数の関数である。

g = (a -> r) なので、その関数は(a -> r)という型のデータを引数にとる。

この引数 (a -> r)自体も関数で、この関数が継続(=この先の計算)を表現している。(たぶん)

Contデータ型は、継続を引数にとり、"その継続を使って最終的な値を計算する方法"を表現した関数である。

returnと bindの定義を見る

instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k)

return aすると、継続を受け取って、その継続にaを渡すだけの計算が作られる。

(>>=)の定義は若干ややこしい。

右辺

Cont $ \k -> c (\a -> runCont (f a) k)

を見ると、bindした結果は、新しいContになる。(あたりまえ)

その新しいContは、次のような計算を行う。

1. その時点での継続 k を受け取る。
2. 合成式の左辺にあった計算cに、継続として(\a -> runCont (f a) k)を渡す
3. この結果、cの計算の結果は、(\a -> runCont (f a) k)に実引数aとして束縛される
4. cの計算結果をfに適用し、その結果得られた計算に、継続としてkを渡す

結果的に、

cの計算をして結果aを得る→そのaをつかって新しい計算(f a)を作る→新しくできた計算(f a)に継続としてkを渡し、最終的な計算結果を得る

という計算が合成される。

callCCの定義を見る

class (Monad m) => MonadCont m where 
    callCC :: ((a -> m b) -> m a) -> m a 
 
instance MonadCont (Cont r) where 
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

callCCは、継続cを引数にとるような計算fを引数にとって、Cont型の計算を返す。

fには、第一引数として、継続 c :: (a -> m b)が渡される。

c :: (a -> m b)なので、この継続の最終的な計算結果自体もCont型。

callCCのinstance宣言の定義にあるとおり、fに渡される継続は (\a -> Cont $ \_ -> k a)という計算。

ここでのポイントは、 Cont $ \_ -> k aという式で、これはその時点での継続 '_'を全く無視してcallCCが呼ばれた時点での継続 k のみを使っている。

これにより、fのなかで、cを呼び出すと、計算f中の継続は無視され、callCCが呼ばれた時点での継続に処理が引き継がれる。(=大域脱出)

。。。

たぶんいろいろ間違っているので、指摘していただけるとありがたいです。(なんじゃそら)