Hatena::ブログ(Diary)

Hatena’s Kitchen RSSフィード

2009-04-07 Haskell勉強会

Haskell勉強会 #1

| 01:12 |  Haskell勉強会 #1を含むブックマーク

誠に恐縮なのですが、チームリーダがチャンスをくれたので、社内で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とかを使ったテストを紹介したかったのですが、諸事情によりほろ酔い状態なので、

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

tom-lpsdtom-lpsd 2009/04/08 01:20 って、本当に反例があった場合は収束しないので last が返ってこなくて、正しくても間違ってても無限ループするという、、、ダメダメですね orz

const ()const () 2009/04/08 19:02 ulam n = (++[1]) $ takeWhile (/=1) $ iterate f n where
 f n = if even n then n `div` 2 else n * 3 + 1
という手も。

tom-lpsdtom-lpsd 2009/04/08 21:39 > const ()さん
なるほどー、iterate!
無限リストにしてtakeWhile、なかなかかっこいいですね。

2009-03-01 Shibuya.lisp#2

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

12:06 |  Shibuya.lisp#2 に行ってきました。を含むブックマーク

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

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

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

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

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

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

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

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

2009-02-03 まだ首が痛い

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

| 00:09 |  Haskellのdata宣言の"!"マークを含むブックマーク

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になるけど、"!"をはずすと何も起こらない。

なるほど。

2009-02-01 首が痛い

HaskellのFFIはとっても簡単

| 23:19 |  HaskellのFFIはとっても簡単を含むブックマーク

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

今17章のFFIのところ。

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

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

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

用意するファイルは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を書いてやることで、直感的に使いやすいインターフェースに改良することができます。

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

2009-01-25 Haskellで継続(Continuation)

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

| 19:34 |  HaskellのContモナドに触れてみるを含むブックマーク

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が呼ばれた時点での継続に処理が引き継がれる。(=大域脱出)




。。。

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