takkan_mのHaskell再挑戦

■ [SICP]パスカルの三角形 20:50

以前、いろんな方が実装していたパスカルの三角形の問題をときました。

表示は手抜き。

$ cat pTriangele.hs 
pTriangle :: Int -> [[Int]]
pTriangle n = cPascal [[]] n 0 1 []
    where
        cPascal :: [[Int]] -> Int -> Int -> Int -> [Int] -> [[Int]]
        cPascal xs n i l ys 
            | n == 0      = tail xs
            | l == i      = cPascal ( xs ++ [ ys ] ) ( n - 1 ) 0 ( l + 1 ) []
            | otherwise   = cPascal xs n ( i + 1 ) l $ makeArray xs i ys
        makeArray :: [[Int]] -> Int -> [Int] -> [Int]
        makeArray xs i ys = flip (:) ys $ getElem xs i
        getElem   :: [[Int]] -> Int -> Int
        getElem   xs i    = addElem ( getPElem xs ( i - 1 ))  ( getPElem xs i)
        addElem   :: Int -> Int -> Int
        addElem   0 0     = 1
        addElem   x y     = x + y
        getPElem  :: [[Int]] -> Int -> Int
        getPElem  _  (-1) =  0
        getPElem  xs i    = selectElemInteger $ drop i $ getPArray xs
                where 
                        selectElemInteger ::  [Int] -> Int
                        selectElemInteger [] = 0
                        selectElemInteger xs = head xs
        getPArray :: [[Int]] -> [Int]
        getPArray = head . reverse

それにしても、引数が多すぎて汚いなぁ。

パターンマッチで一度引数書いたら、その関数の別の定義はポイントフリーで書けないのね。初めて知りました。

こんな感じでは、書けないんですね。

hoge :: [a] -> a
hoge [] = 0
hoge = head

実行結果はこちら

$ ghci pTriangele.hs 
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( pTriangele.hs, interpreted )
Ok, modules loaded: Main.
*Main> pTriangle 3
[[1],[1,1],[1,2,1]]
*Main> pTriangle 4
[[1],[1,1],[1,2,1],[1,3,3,1]]
*Main> pTriangle 7
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]

■ 逆ポーランド記法 01:13

はてなダイアリーで書いている方の日記で最近カロリー計算(ただ数字をたしているだけ)のためにてきとうなプログラムを書くというのをしているのですが、５日目にしてネタにつきたので、逆ポーランド記法の計算機をつくりました。

haskell taka$ cat rPo.hs 
rPo :: String -> Integer
rPo str = evalPo [] $ words str
    where
        evalPo :: [Integer] -> [String] -> Integer
        evalPo l []     = head l
        evalPo l (x:xs) = if elem x exprs
                            then flip evalPo xs $ flip  evalExpr l $  getExpr x 
                            else flip evalPo xs $ flip (:) l $ strToInteger x
        exprs = [ "+" , "-" , "*" , "/" ]
        getExpr :: String -> ( Integer  -> Integer -> Integer)
        getExpr x
            | x == "+" = (+)
            | x == "-" = (-)
            | x == "*" = (*)
--          | x == "/" = (/)
        strToInteger = (read :: String -> Integer)
        evalExpr :: (Integer -> Integer -> Integer) -> [Integer] -> [Integer]
        evalExpr ex (x:y:xs) = flip (:) xs $ ex y x

testData = [ ( rPo , "390 1042 + 191 204 + +" , 1827) ,
             ( rPo , "365 328 + 210 + 191 + 577 90 + +" , 1761),
             ( rPo , "380 432 165 60 135 292 80 + + + + + +", 1544),
             ( rPo , "288 857 37 + + 185 + 204 + 85 +" , 1656),
             ( rPo , " 3 2 + 4 * 4 -" , 16)]

testEql :: (Eq b) => [ ( ( a -> b) , a , b) ] -> [ (Bool,b,b) ]
testEql = map (\(x,y,z) -> ((z ==( x y)) , (x y) , z))

文字列から数値の変換がわからなかったので趣味的にっきさんからstrToIntegerは拝借させていただきました。readでやるのね。

(/)をコメントアウトしているのは、(/)の型をまちがえてIntegerでつくってしまったため。ちょっと睡魔が襲ってきているので、起きたら対応するかも。

で、testEqlというテスト関数を作ってみた。関数とその引数と期待値のタプルを要素とした配列をもらい、その比較結果と値のタプル配列を返す。全部Trueなら成功。

実行結果はこちら

*Main> testEql testData
[(True,1827,1827),(True,1761,1761),(True,1544,1544),(True,1656,1656),(True,16,16)]

最初は、最後のデータでFalseになった。理由はevalExprを

evalExpr ex (x:y:xs) = flip (:) xs $ ex x y

としてしまい、(False,-16,16)だって。スタックから数値を取り出して適用する順序を間違ってしまいました。

もっと、すっきり書けないかなぁ。

■ ($)と(.)の違いを考えてみた 10:24

Yet Another HaskellのExersize3.2の問題を解こうとしてはまりました

英語が苦手なので問題の意味がよく分かっていないかもしれませんがしていされたタプルからfstとsndで文字をとりだせと解釈した

指定されたタプルは

(1,'a'),"foo")

で、こんなかんじでやっってみた。

Prelude> let outOfChar  = ( snd.fst t , snd t)

で、おこられた。

Prelude> outOfChar ((1,'a'),"foo")

<interactive>:1:11:
    Couldn't match expected type `a1 -> (a, b)'
           against inferred type `(a11, b1)'
    In the expression: (1, 'a')
    In the first argument of `outOfChar', namely `((1, 'a'), "foo")'
    In the expression: outOfChar ((1, 'a'), "foo")

とりあえず、型をみると

Prelude> :t ( snd . fst)
( snd . fst) :: ((a, b), b1) -> b

あっていそうである。でも、何故はじかれるのだろう？

よくわからないので、(.)を($)にかえてみる。

Prelude> let outOfChar t = ( snd $ fst t , snd t) 
Prelude> outOfChar ((1,'a'),"foo")
('a',"foo")

これは、大丈夫。(.)も($)もあとの関数に最初の関数をくっつけるものとしての認識だったのだが。

しばらく悩んでみると、関数の適用がHaskellでは最優先されるということを思い出す。なので、(.)を使った方は、

snd . (fst t)

と解釈されてしまい、失敗したのではないだろうか？これでは、fst t はaがかえってくることになるから、型エラーになっているのではないのか？($)の場合、適用した値(といっていいのだろうか？)がsndに渡されるので成功したのか。試しに、適用順を括弧でやってみる

Prelude> let outOfChar t = ( ((snd . fst) t) , snd t)
Prelude> outOfChar ((1,'a'),"foo")
('a',"foo")

成功した。

snd . fst tなどの型をみてみると、

Prelude> let t =((1,'a'),"foo")
Prelude> :t snd . fst t

<interactive>:1:6:
    Couldn't match expected type `a -> (a1, b)'
           against inferred type `(Integer, Char)'
    In the second argument of `(.)', namely `fst t'
Prelude> :t fst t
fst t :: (Integer, Char)
Prelude> :t snd
snd :: (a, b) -> b
Prelude> :t snd . fst
snd . fst :: ((a, b), b1) -> b

snd .fst tのもとめられている、a -> (a1,b)は、どの部分の型なのだろうか？

なんとなく、こういうときの対処は、わかるようになったけど、どうもうまくつかめないなぁ。cでポインタにはまったときのような気分。

■ 問題7.10 20:47

以下のパターンに対し指定されたメッセージを返すプログラム。

___1 my single ___2 me ___3
    -> tell me about your single
___1 i am ____2
    -> i am sorry to hear you are ___2
___1 am i ___2
    -> do you believe you are ___2
___1 you ___2 me
    -> why do you think i ___2 you
___1
    -> in what way

で、こんな感じに。

getWhyMessage mes = "why do you think i " ++ mes ++ " you"
getDoYouMessage mes = "do you believe you are " ++ mes
getSorryMessage mes = "i am sorry to hear you are " ++ mes
getTellMeMessage mes = (++) "tell me about your" $  getPart "" mes
		   where
			getPart mes (x:xs) = if x == "me"
						then mes
						else getPart (unwords [mes, x] ) xs



getMessage [] = return "in what way"
getMessage (x:xs) | x == "my"  = if elem "me" xs
				  then return $ getTellMeMessage xs
				  else getMessage []
		  | x == "i"   = if head xs == "am"
				  then return $ getSorryMessage $ unwords $ tail xs
				  else getMessage []
		  | x == "am"  = if head xs == "i"
				  then return $ getDoYouMessage $ unwords $ tail xs
				  else getMessage []
		  | x == "you" = if last xs == "me"
				  then return $ getWhyMessage $ unwords $ init xs
				  else getMessage []
		  | otherwise  = getMessage xs

echoLines = do line <- getLine
	       if line == "exit" 
		    then return ""
		    else do message <- getMessage $ words line
			    putStrLn message
			    echoLines
			    return  ""

main = do echoLines

$ ./main
well my friend made me come here
tell me about your  friend made
he says i am depressed
i am sorry to hear you are depressed
i think i need help
in what way
oh am i making sense so far
do you believe you are making sense so far
you are making fun of me
why do you think i are making fun of you

ホントは、入力のところに">"のようにプロンプトをだしたかったんだけど、getLineの前にputStrをおいても出力されるのが、応答メッセージのあとになっちゃったんだよね。flushしなきゃいかんのかなぁ。

■ Parsecの疑問 21:57

ひさしぶりに、プログラミング言語の概念と構造の問題を解いていて、elizaのようなプログラムの問題があったんだけど(問題をといたエントリはたぶん後で書く)、入力された文を解析してテンプレにあてはめて返すという処理をしなくちゃいけないので、Parsecを使おうかと思った。しかし、ここでちょっと疑問が発生した。

Parsecって、細かいパーサーを合成してひとつのパーサーを作るわけで、

bigParse = smallParse1
        <|>smallParse2
        <|>smallParse3

みたいに書くわけで(ひとつのパーサーが失敗したときのエラー処理はここでは省略)、このパーサーの評価方法というか順序がどうなっているかということに疑問をもった。このまま評価した場合って、smallParse3を評価して、失敗したらsmallParse2を評価してみたいになるのかな？それとも、裏側では小人さんがsmallParse1、smallParse2、smallParse3を同時にやっているのかな？

<|>はモナドになるから順序がかかわってくるから、順にやってるのかなぁ？

うーん。まだまだ、わからないことばかりだ。