HaHaHa!(old)

2008-11-06

lines と unlines に関して

no title

での言及にひとこと。

(コメントの書き方がわからなかったのでこちらに)

Haskellの嫌なところ。文字列を行ごとに分割・結合するlines・unlines関数が嫌い。たとえば、「lines "test"」も「lines "test\n"」も、どちらも"test"が返ってくる。違うものを入力して同じ結果が返ってくるというのは、美しくない。集合の写像が一意でなくなったら、可逆な変換が行えなくなってしまう(あとで元通りに戻そうと思ったときにできなくなる)。その結果、プログラミングの力は著しく削がれてしまう。

linesとunlinesが対象としているのは、いわゆるUnix流にいうところのテキストファイルで、テキストファイルは行の集合で、行は末尾が改行で終る文字列なんだと思います。つまりテキストファイルの中身のテキストは必ず改行で終る文字列です。lines 改行をセパレータではなく、行のターミネータとしてみているということです。厳密には、linesの引数は改行で終る文字列でなければならないので lines "test" はエラーにすべきかもしれませんが、それじゃあんまりなので終端が末尾ではない文字列に対しては末尾に改行を補っているかのように動作させているのだと思います。

unlinesはすべての文字列の後ろに改行を付けていることからも、改行をターミネータとみなしていることが納得できますよね(納得してね:))。というわけで、linesとunlines はちゃんと逆変換になっていると。。。

2008-09-28

モナド則を満たすべき理由

モナド則ふたたびに対してコメントしたのですが、うっかりして、コード部分のインデントが崩れてしまったのでここに再掲


型の上では「整合性」が取れているので、「整合性」が取れない例というのは示しにくそうです。

モナド則が「あたり前だ」と感じるということは、モナド則が満たされることを暗黙に期待しているということですよね。つまり、モナド則が満されないないことがあれば、そんなのは役に立たないというか、使い道がなさそうではあります。

モナド則を満さなければ、役に立たない」ことの証明は、私には、うまくできそうにないけど、「モナド則を満たさず、かつ、役に立たない」Monad クラスインスタンスなら意図的に作れます。

data List a = Nil | Cons a (List a)

toPrimList :: List a -> [a]
toPrimList Nil = []
toPrimList (Cons x xs) = x : toPrimList xs

instance Show a => Show (List a) where
  show = show . toPrimList

instance Functor List where
  fmap f Nil         = Nil
  fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Monad List where
  return x = Nil                         -- モナド則 2 を満たさない
  l >>= f  = fold append Nil (fmap f l)
     where append Nil         ys = ys    -- (++) 相当
           append (Cons x xs) ys = Cons x (append xs ys)
           fold f z Nil = z              -- foldr 相当
           fold f z (Cons x xs) = f x (fold f z xs)

ps = Cons 1 (Cons 2 Nil)                 -- [1,2] 相当
qs = Cons 'a' (Cons 'b' (Cons 'c' Nil))  -- ['a','b','c'] 相当

sample = do p <- ps
            q <- qs
            return (p,q)

sample の値として期待したいのは [ (p,q) | p <- ps, q <- qs ] すなわち

[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c')]

相当の List (Int,Char) 型の値だけれど、このモナドの実装ではそうなっていません。

return の実装を

return x = Cons x Nil

にしてモナド則を満すようにすると sample は期待したい値になります。

kazu-yamamotokazu-yamamoto2008/09/29 13:50山本です。お答え頂き、ありがとうございます。
今回の考察で、モナド則2が重要なのは分りました。できればモナド則3を満たさないとおかしくなる例があると、嬉しいのですが。。。

KailashKailash2012/07/24 01:24That's a mold-breaker. Great tinhking!

kxnthkmqmpkxnthkmqmp2012/07/26 18:097mi5UW <a href="http://hoinevmlwpoz.com/">hoinevmlwpoz</a>

2008-09-26

compact-number-list

http://d.hatena.ne.jp/higepon/20080925/1222326246

どこかで見た気がするんだけどなぁ

compactNumberList :: (Enum a, Eq a) => [a] -> [[a]]
compactNumberList [] = []
compactNumberList (x:xs) = reverse $ foldl f [[x]] xs
  where f a@(b:bs) y = case (head b,last b) of
                         (p,q) | succ q == y -> [p,y]:bs
                         _                   -> [y]:a

どこかというのはここ→http://builder.japan.zdnet.com/sp/ruby-doukaku-panel/story/0,3800086254,20369264,00.htmだった。

出力の仕様だけあわせてみた。

import Data.List 

data Compact a = S a | P a a

instance Show a => Show (Compact a) where
  showsPrec _ (S x)   = shows x
  showsPrec _ (P x y) = shows x.("-"++).shows y
  showList = foldr (.) id . intersperse (", "++) . map shows 

compactNumberList :: (Enum a, Eq a) => [a] -> [Compact a]
compactNumberList []     = []
compactNumberList (x:xs) = reverse $ foldl f [S x] xs
  where f (S b:bs)   y | succ b == y = P b y:bs
        f (P b c:bs) y | succ c == y = P b y:bs
        f bs         y               = S   y:bs

実行例

*Main> compactNumberList [1,3,4,5,6,12,13,15]
1, 3-6, 12-13, 15
*Main> compactNumberList $ map head $ group $ sort $ filter (' '/=) $ "This book is dedicated, in respect and admiration, to the spirit that lives in the computer."
',', '.', 'T', 'a'-'e', 'h'-'i', 'k'-'p', 'r'-'v'

Gaucheで書きなおした

(use util.match)
(define (compact-number-list xxs)
  (define (f x y)
    (match y (((a . b) . c) (if (= (+ b 1) x) (cons (cons a x) c) (cons x y)))
             ((a       . c) (if (= (+ a 1) x) (cons (cons a x) c) (cons x y)))))
  (match xxs (() ()) ((x . xs) (reverse (fold f (list x) xs)))))

higeponhigepon2008/09/26 14:51うお。短い。

shiroshiro2008/09/27 03:37おー、これは綺麗だ。

2008-09-04

Gauche/Kahuaセミナー2008 Fall 開催のご案内(終了しました)

Kahuaプロジェクト、HOPプロジェクトは2008年09月13日に下記の

要領でGauche/Kahuaセミナー2008 Fallを開催します。

開催要領

  • 表題:「Gauche/Kahuaセミナー2008 Fall」
  • 日時:2008年9月13日(土) 13:30 ~ 17:30
  • 場所:秋葉原ダイビル13F東京大学情報理工学系研究科秋葉原拠点
  • 主催: Kahuaプロジェクト、HOPプロジェクト
  • 協力: 東京大学情報理工学系研究科創造情報学専攻
  • 定員: 40名
  • 参加費:無料

講演内容:

  • (Gauche on Rails)への道

吉田裕美 (EY-Office)

  • Kahuaプログラミングスタイル

備前達矢 (タイムインターメディア)

参加登録

終了しました

oskimuraoskimura2008/09/10 09:26行きたいけど、当日予定がバッティングしまくりorz

2008-07-18

3not problem

和田先生のBlogにあった3not problemをやってみた.ヒントを理解するのに時間がかかった.

解を Haskell で表現してみました.[Bool] :-> [Bool] という素子を考え回路を

表現してみました.(表現したことになるかどうか...)

  • AND,OR それに NOT 素子.
  • NOP (n入力に拡張したものも含む)
  • split (スプリッタ),cross (線の交差),swap (複数線の交差) のような回路操作子
  • (->-) 素子接続結合子,-|- 素子積載結合子
スプリッタ(split 3)
     +---+     
     |   +--->a
     |   |     
     |   +--->b
a--->+   |     
     |   +--->c
b--->+   |     
     |   +--->a
c--->+   |     
     |   +--->b
     |   |     
     |   +--->c
     +---+     
   素子接続結合子 GT1 ->- GT2
                      
     +---+                   +---+
     |   +--->           --->+   |
x--->+   |                   |   |
     |GT1+--->    ->-    --->+GT2+--->z
y--->+   |                   |   |
     |   +--->           --->+   |
     +---+                   +---+
               
            +-------------+
            |             |
       x--->+             |
            | GT1 ->- GT2 +--->z
       y--->+             |
            |             |
            +-------------+
   素子積載結合子 GT1 -|- GT2
                      
     +---+     
x--->+   |     
     |GT1+--->z
y--->+   |                     +-----------+
     +---+                x--->+           +--->z
                               |    GT1    |
      -|-                 y--->+    -|-    +--->q
                               |    GT2    |
     +---+                p--->+           +--->r
     |   +--->q                +-----------+
p--->+GT2|
     |   +--->r
     +---+     
{-# LANGUAGE TypeOperators #-}
import Control.Arrow

type a :-> b = a -> (b, a)
type Gate = [Bool] :-> [Bool]

-- primitive

nop :: Gate
nop = nopn 1

nopn :: Int -> Gate
nopn = splitAt

gNOT :: Gate
gNOT = gNOTn 1
  where gNOTn n = (map not *** id) . args n

gAND :: Gate
gAND = gANDn 2
  where gANDn n = (return . and *** id) . args n

gOR :: Gate
gOR = gORn 2
  where gORn n =  (return . or *** id) . args n

---- Combinators

infixr 3 -|-
infixr 2 ->-

(-|-) :: Gate -> Gate -> Gate       -- stack gates
g -|- h = (append . (fst &&& fst . snd) &&& snd . snd) . second h . g

(->-) :: Gate -> Gate -> Gate       -- connect gates
g ->- h = h . append . g

---- Circuit operators

split :: Gate              -- fork a line
split = splitn 1

splitn :: Int -> Gate      -- fork n lines (n lines into 2n lines)
splitn n = (((++) <*> id) *** id) . args n

cross :: Gate              -- cross 2 lines
cross = crossn 2

crossn :: Int -> Gate      -- cross n lines
crossn n = (reverse *** id) . args n

swap :: (Int,Int) -> Gate  -- swap m lines and n lines
swap (m,n) = s
  where s xs = case splitAt m xs of
          (xs',ys) -> case splitAt n ys of
             (ys',zs) -> (ys'++xs',zs)

--- Utilities

args    = splitAt
append  = uncurry (++)
f <*> g = uncurry id . (f &&& g)

-- g0OR1 : P : 0 or 1 True in the input
-- 3 inputs :-> 1 output
-- 2 ANDs, 2 ORs, 1 NOT
g0OR1 :: Gate 
g0OR1 = (nop -|- (splitn 2 ->- (gOR -|- gAND)))
    ->- (gAND -|- nop)
    ->- gOR
    ->- gNOT
{-
 a ----------------,   +-----+
          +-----+  '-->+     |
 b ---,-->+     |      | AND +--,
      |   | OR  +----->+     |  |   +-----+
 c -,-|-->+     |      +-----+  '-->+     |    +-----+
    | |   +=====+                   | OR  +--->+ NOT +--->
    | '-->+     |         ,-------->+     |    +-----+
    |     | AND +---------'         +-----+
    '---->+     |
          +-----+
-}

-- g0OR2 : Q : 0 or 2 Trues in the input
--       : 4 inputs (A,B,C,P) :-> 1 output Q
-- 3 ANDs, 3 ORs, 1 NOT
g0OR2 :: Gate
g0OR2 = ((splitn 3 ->- (((nop -|- gAND) ->- gAND) -|- ((nop -|- gOR) ->- gOR))) -|- nop)
    ->- (nop -|- gAND)
    ->- gOR
    ->- gNOT

-- g012 : 3 inputs (A,B,C) :-> 2 outputs (P,Q)
-- 5 ANDs, 5 ORs, 2 NOTs
g012 :: Gate
g012 = splitn 3
   ->- (nopn 3 -|- (g0OR1 ->- split))
   ->- (g0OR2  -|- nop)

-- g1NEG : 4 inputs (P,Q,A,B) :-> 1 output (~C)
-- 4 ANDs, 3 ORs
g1NEG :: Gate
g1NEG = (nop -|- (    (split -|- splitn 2)
                  ->- (nop -|- cross -|- nop -|- gAND)
                  ->- (gAND -|- split -|- nopn 2)))
    ->- (gOR -|- nop -|- cross -|- nop)
    ->- (nop -|- gAND -|- gOR)
    ->- (gOR -|- nop)
    ->- gAND

-- g3NOT : 3 inputs (A,B,C) :-> 3 outputs (~A,~B,~C)
-- 17 ANDs, 14 ORs, 2 NOTs
g3NOT :: Gate
g3NOT = splitn 3
    ->- ((g012 ->- splitn 2 ->- (nopn 2 -|- splitn 2)) -|- splitn 3)
    ->- (nopn 4 -|- swap (2,2) -|- nopn 4)
    ->- (nopn 2 -|- swap (2,2) -|- swap (2,2) -|- nopn 2)
    ->- (g1NEG -|- g1NEG -|- g1NEG)
    ->- crossn 3

---- test 

bools :: [Bool]
bools = [minBound..maxBound]

cases :: [[Bool]]
cases = [ [a,b,c] | a <- bools, b <- bools, c <- bools ]

test3 g = and $ map (and . (zipWith xor <*> (fst . g))) $ cases

True  `xor` q = not q
False `xor` q = q

JanayaJanaya2012/10/03 00:18Many many qualtiy points there.

gmpgazgmpgaz2012/10/03 19:275tz9Qg <a href="http://wzerabqymndu.com/">wzerabqymndu</a>

iqmuqjjxdiqmuqjjxd2012/10/04 00:096FyU1Y , [url=http://iszsvkuugtpe.com/]iszsvkuugtpe[/url], [link=http://kmtxnbmytrcp.com/]kmtxnbmytrcp[/link], http://gdeswagojsxc.com/

xkgsslcqxkgsslcq2012/10/04 12:52W6xOpX <a href="http://kvbmauqvdwxk.com/">kvbmauqvdwxk</a>

niowymbqqmniowymbqqm2012/10/06 14:00woLhWM , [url=http://clzssfzdopxq.com/]clzssfzdopxq[/url], [link=http://xptwsndokarn.com/]xptwsndokarn[/link], http://jfnfztojkeae.com/

2008-04-07

生徒になってくれる人募集(締め切りました)

Haskellプログラミングは楽しいよ」.でもじゃあどのようにHaskellプログラミングにアプローチすればいいのかを丁寧に説明できないでいます.「慣れて下さい」としか言えないのではあんまりですよね.私自身はすっかりHaskell脳になっているので,初めてHaskellプログラミングに触れたときの困惑が理解できないでいます.いや.理解できないのではなく,気づかないというほうが近いかもしれません.

Haskellプログラミングをはじめた頃の苦労や感動を思い出したいなぁ.

でもどうすれば...

Haskellプログラミングをだれかに教えよ」と家訓にもある(そんなわけはない:p).

というわけで,対面でHaskellプログラミングの楽しみ方を教えます.

継続的に生徒になってくれる奇特な方(1〜3名)を募集します.

(こちらからお願いしていて申しわけありませんが,交通費や謝礼などは出ません).

  • 週に 1回あるいは2週に1回
  • 1回 2〜3時間程度
  • 4〜6ヶ月程度

を予定しています.プログラミング一般の知識は前提としません.Haskellプログラミングに興味のある入門者の方ならどなたでもどうぞ.(億万が一,たくさん応募があった場合にはお断りすることもあることをおゆるし下さい.)

教材はこちらで用意します.時間と場所は相談してきめましょう.

興味のある方は lec at haskell dot jp までメールをお願いします.

ここでアナウンスしても読んでいる人はそんなにいないだろうし,たまたま辿りついた人はたぶん入門者じゃない気もするが...

(2008-04-09):追記

コメントをいただきありがとうございます.

想定しているのは,

  • 場所:東京で私の職場(曙橋)から遠くないどこか
  • 目的:Haskellプログラミングを楽しむ
  • 内容:Haskellプログラミングの初歩から
    • Haskellプログラミングの気分とか心が伝わるような内容
    • プログラミングの経験もあまりない方が理解でき,Haskellプログラミングが楽しめるような内容
    • プログラミング基礎理論などの難しい話は(できないので)ありません
  • 対象:Haskellプログラミングに興味があり,かつ
    • プログラミングの経験があまりない方
    • 関数プログラミングは未経験あるいはほとんど経験がない方
    • 経験はあるけれど,初歩からの内容でも退屈しないで楽しんでくれる方

(2008-04-11):追記

締切ました.ご応募ありがとうございました.

JoeJoe2008/04/08 22:47私は、学ぶ興味があるけど、たぶん会える時間がなかなか作れないかも。オンラインでやる可能性は? -Joe

alekseialeksei2008/04/09 00:13凄く興味がある入門しようとしているレベルのものですが
東京近辺なのでしょうか?

ささだささだ2008/04/09 03:29うちの学生に聞いてみます?

nishiohirokazunishiohirokazu2008/04/09 18:04興味津々ですけど「プログラミングの経験があまりない方」には該当しなさそう…
講義の内容が録画されて後から見られるような状態になっていると、
後から知った人や遠くて参加できない人にもいいかもしれませんね。

2008-04-03

Project Euler - Problem 24

順列を辞書順に生成してたどるという素朴なものだと遅すぎる...

import Data.List

euler024 :: [a] -> Integer -> [a]
euler024 xs n = unfoldr phi (n-1,xs,fs)
  where fs = scanr (*) 1 [l,l-1 .. 1]
        l  = genericLength xs - 1
        phi (_,_,[])  = Nothing
        phi (m,ls,fs) = Just (z,(r,ys++zs,tail fs))
          where
             (q,r) = m `divMod` head fs
             (ys,z:zs) = genericSplitAt q ls