takkan_mのHaskell再挑戦 RSSフィード

2007-03-04

[]パスカル三角形 20:50 パスカルの三角形 - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - パスカルの三角形 - takkan_mのHaskell再挑戦 パスカルの三角形 - takkan_mのHaskell再挑戦 のブックマークコメント

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

表示は手抜き。

$ 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]]

VerucaVeruca2016/05/10 22:21Hey There. I found your blog using msn. This is a really well written article. I&8;217#ll make sure to bookmark it and come back to read more of What Sticks: The History of Adhesive Tape | . Thanks for the post. I’ll certainly return.

2007-03-02

逆ポーランド記法 01:13 逆ポーランド記法 - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - 逆ポーランド記法 - takkan_mのHaskell再挑戦 逆ポーランド記法 - takkan_mのHaskell再挑戦 のブックマークコメント

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

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)だって。スタックから数値を取り出して適用する順序を間違ってしまいました。

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

KarimeKarime2012/05/05 10:44That's a smart answer to a tricky qstueion

RameshRamesh2013/07/27 11:04A simple and innlielgett point, well made. Thanks!

TolgaTolga2013/07/29 19:34It's a pleasure to find such raaiontlity in an answer. Welcome to the debate.

VebyVeby2013/07/30 11:23As Charlie Sheen says, this article is <a href="http://wwceiyjpsq.com">"WNI!INGN"</a>

AlmogAlmog2013/07/31 04:29Awesome you should think of sotnhmieg like that http://pzlmmii.com [url=http://sabwatj.com]sabwatj[/url] [link=http://jdcivzkkvm.com]jdcivzkkvm[/link]

LisaLisa2013/07/31 13:16<a href=\"http://qicnzp.com\">Kngldewoe</a> wants to be free, just like these articles!

AbidAbid2013/07/31 18:55If you're reading this, you're all set, padrren! http://djytknvavcd.com [url=http://abirktt.com]abirktt[/url] [link=http://qcqxweqocp.com]qcqxweqocp[/link]

2006-12-23

($)と(.)の違いを考えてみた 10:24 ($)と(.)の違いを考えてみた - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - ($)と(.)の違いを考えてみた - takkan_mのHaskell再挑戦 ($)と(.)の違いを考えてみた - takkan_mのHaskell再挑戦 のブックマークコメント

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

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

指定されたタプルは

(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でポインタにはまったときのような気分。

takatohtakatoh2006/12/24 15:22Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
の a -> b がここでは a -> (a1, b) にあたるんではないかと。

takkan_mtakkan_m2006/12/26 21:06あー。もしかして、sndがタプルを引数にとるから、1引数でタプルを返す関数を必要としているのに、タプルがきているっていうことにたいしての警告文なんですね。ありがとうございます。

GamzeGamze2012/12/20 02:11This is a ralely intelligent way to answer the question.

lenfgvgxlenfgvgx2013/04/04 20:04SjXfzz , [url=http://fesxvewnhrkq.com/]fesxvewnhrkq[/url], [link=http://nkjtajbsdxaj.com/]nkjtajbsdxaj[/link], http://trtlrtzbimia.com/

2006-12-03

問題7.10 20:47 問題7.10 - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - 問題7.10 - takkan_mのHaskell再挑戦 問題7.10 - takkan_mのHaskell再挑戦 のブックマークコメント

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

___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しなきゃいかんのかなぁ。

RuthRuth2012/10/02 19:25If information were soccer, this would be a goooaool!

dheezzxhxdheezzxhx2012/10/03 19:051ryJyU <a href="http://bkdwfjybvagi.com/">bkdwfjybvagi</a>

bzocpomgsbzocpomgs2012/10/03 23:44ljjkyP , [url=http://wnntjpqfzonh.com/]wnntjpqfzonh[/url], [link=http://qugurvyhrowf.com/]qugurvyhrowf[/link], http://yzoelxmdycmu.com/

kdrtcmfjkdrtcmfj2012/10/04 12:29QDIiks <a href="http://whjqvwxmhmip.com/">whjqvwxmhmip</a>

udurcznpfvcudurcznpfvc2012/10/06 13:38FLDc3p , [url=http://nsactwwocurn.com/]nsactwwocurn[/url], [link=http://gtyfgqysdjja.com/]gtyfgqysdjja[/link], http://kxgyzozhfoqj.com/

2006-11-23

Parsecの疑問 21:57 Parsecの疑問 - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - Parsecの疑問 - takkan_mのHaskell再挑戦 Parsecの疑問 - takkan_mのHaskell再挑戦 のブックマークコメント

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

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

bigParse = smallParse1
        <|>smallParse2
        <|>smallParse3

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

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

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

jmkjmk2006/11/23 22:351→2→3の順番で計算され、最初に成功したパースの結果が返されます。
Parsecのパーサはようするに関数なので「評価」というと少し違う気もしますが。

takkan_mtakkan_m2006/11/25 22:05解説ありがとうございます。1->2->3の順番で計算されるとういうことは、1、2、3ともに入力を最後までたどって失敗というときは、ものすごく計算量がおおくなって非効率的にかんじてしまうんですが。効率考えると、自分で、パターンマッチング駆使して書いた方がいいんでしょうか?

jmkjmk2006/11/26 01:59確かに、まず1を失敗するところまで試し、それから2を失敗するところまで試し、3を失敗するところまで試さないと完全にパースに失敗したかどうかはわかりません。しかし、パーサとはそもそもそういうものではないでしょうか。
パターンマッチングを駆使する、というのがどのような処理を念頭に置かれているか想像できないので、そちらはわかりませんが。

takkan_mtakkan_m2006/11/26 19:55またわかりづらいコメントを書いてしまいすいません。
mainParser (x:xs) = x of
isAlpha x -> parseAlpha xs
isDigit x -> parseDigit xs
のような感じでやったほうが、効率がよいのかなと思ったんですが、結局失敗したら戻ってパースしたりするから、同じなのかもしれないですね。

LuljetaLuljeta2013/03/29 14:31Surprising to think of soemthnig like that

xmggebigzwxmggebigzw2013/03/30 14:23HygUfH <a href="http://qxlpgsiceiwm.com/">qxlpgsiceiwm</a>

ycpwrmycpwrm2013/04/01 10:42JDVOro , [url=http://wwkygcdycknf.com/]wwkygcdycknf[/url], [link=http://smqjicmvlnwv.com/]smqjicmvlnwv[/link], http://yikinnrjcoev.com/