takkan_mのHaskell再挑戦 RSSフィード

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/

2006-11-20

僕もJoelの問題を解いてみよう 22:16 僕もJoelの問題を解いてみよう - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - 僕もJoelの問題を解いてみよう - takkan_mのHaskell再挑戦 僕もJoelの問題を解いてみよう - takkan_mのHaskell再挑戦 のブックマークコメント

結城さんのSICP日記を見て、自分も解きたくなったので解いてみた。

あたえられた関数を使い、リストの平方和を求めるという問題。あたえられた関数というのがもともと、Scheamやらjavascriptでかかれているので、とりあえずHaskellに置き換えてみる。

--見た目の都合で変なところで改行しています。
accumulate _ a [] = a
accumulate combiner null_value (x:xs) = combiner x $               
                            accumulate combiner null_value xs

で、これを使い、リストの平方和を求める関数を書いてみる。

sum_of_squares = accumulate combi 0
                 where
                        combi a b = a ** 2 + b

で、実行。

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

Loading package base-1.0 ... linking ... done.
Compiling Main             ( try.hs, interpreted )
Ok, modules loaded: Main.
*Main> sum_of_squares [1..5]
55.0

規則性のある連続するリストを書くのが楽なのは、ホントHaskellのいいところだと思う。でも、このままだと、(**)のおかげて、小数点がでてしまいださいので、ちょっと細工を。

*Main> let sum_of_squares' = fromEnum . sum_of_squares
*Main> sum_of_squares' [1..5]
55

http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3AfromEnum :title=fromEnum]でIntに変更してあげてやる。これで、Intが返るのでOK.

追記:まぁ条件が無ければ畳み込んでしまえば1行ですんでしまうんですけどね

Prelude> let sum_of_squares'' = foldr (\ x -> (+) $ x ** 2) 0
Prelude> sum_of_squares'' [1..5]
55.0

nobsunnobsun2006/11/21 10:51(**)のかわりに(^)を使うのがいいかも。
foldl (flip ((.).(+)) (^2)) 0 [1..5] とか。。。

takkan_mtakkan_m2006/11/21 21:59(^)だとNumが返ってくるんですね。flipを使った関数の((.).(+))の部分は、今の僕には、パズルです。

takatohtakatoh2006/11/23 14:30flip ((.).(+)) (^2)
--> (\x -> flip ((.).(+)) (^2) x)
--> (\x -> ((.).(+)) x (^2))
--> (\x -> (((.).(+)) x) (^2))
--> (\x -> ((.) (x+)) (^2))
--> (\x -> (.) (x+) (^2))
--> (\x -> (x+).(^2))
--> (\x y -> ((x+).(^2)) y)
--> (\x y -> (x+) (y^2))
--> (\x y -> x + y^2)
かな。x と y が逆ですね。あ,foldl を使ってるからこれで良いのか。

takkan_mtakkan_m2006/11/23 21:29takatohさん解説ありがとうございます。最初、((.).(+))の最初の
(.)の必要性がわからず、(^2)と合成させたいんなら、(.) (+)だけでいいじゃないかと思ってましたが、(^2)と合成前にxを適用させておきたいから、もうひとつ(.)が必要なんですね。
勉強になります。

DawsonDawson2012/05/03 03:47A few years ago I'd have to pay someone for this infromtiaon.

ryyeykforyyeykfo2012/05/03 11:1779SekB <a href="http://pkrdwkhmfgxi.com/">pkrdwkhmfgxi</a>

dfafrfdfafrf2012/05/04 09:10z6DHXG , [url=http://vhulvwrfmbke.com/]vhulvwrfmbke[/url], [link=http://rhmhrtllygeb.com/]rhmhrtllygeb[/link], http://kvvgniuceato.com/

akreiybvtakreiybvt2012/05/05 10:48pkPwIa <a href="http://zzjpnpewctrb.com/">zzjpnpewctrb</a>

kswhjlxkswhjlx2012/05/05 15:12yMrTaN , [url=http://gaqdtrfumwyx.com/]gaqdtrfumwyx[/url], [link=http://ptqfbfkssgvm.com/]ptqfbfkssgvm[/link], http://aivflhupkosc.com/

2006-11-18

List.sortはよきにはからってくれているんですね 13:09 List.sortはよきにはからってくれているんですね - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - List.sortはよきにはからってくれているんですね - takkan_mのHaskell再挑戦 List.sortはよきにはからってくれているんですね - takkan_mのHaskell再挑戦 のブックマークコメント

ちょっとした、データをタプルで表現したときに、そのリストをList.sortでソートしたいときは、新しい型をつくって、ordインスタンスにして、関数を定義しなきゃいけないと思っていたんですが、そこはちゃんとよきにはからってくれるんですね。

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

Loading package base-1.0 ... linking ... done.
Prelude> :m List
Prelude List> let tlist = [ ("hoge",4) , ("moge", 3),("foo",6),("bar",2)]
Prelude List> sort tlist
[("bar",2),("foo",6),("hoge",4),("moge",3)]
Prelude List> let rlist = map (\ xs -> ( snd xs , fst xs) ) tlist
Prelude List> map (\xs -> (snd xs ,fst xs)) tlist
[(4,"hoge"),(3,"moge"),(6,"foo"),(2,"bar")]
Prelude List> sort rlist
[(2,"bar"),(3,"moge"),(4,"hoge"),(6,"foo")]
Prelude List> let slist = (4,"jojo") : rlist
Prelude List>  (4,"jojo") : rlist
[(4,"jojo"),(4,"hoge"),(3,"moge"),(6,"foo"),(2,"bar")]
Prelude List> sort slist
[(2,"bar"),(3,"moge"),(4,"hoge"),(4,"jojo"),(6,"foo")]
Prelude List>

昔作った単語の頻度カウントを作りなおしてみた 14:05 昔作った単語の頻度カウントを作りなおしてみた - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - 昔作った単語の頻度カウントを作りなおしてみた - takkan_mのHaskell再挑戦 昔作った単語の頻度カウントを作りなおしてみた - takkan_mのHaskell再挑戦 のブックマークコメント

せっかく、nobsunさんにgroup関数を教えてもらったので、昔作った単語の頻度カウントソート機能をつけてみた。大元ネタこちら

import List
import System
import System.IO

makelist  = group .sort. words

makeWCList xs  = map (\ys ->  ((head ys) ,(length ys))) ( makelist xs)

freqsort = sort.map (\ xs -> ( snd xs , fst xs))

sortWCList = reverse.freqsort.makeWCList

putsWCList   = print . sortWCList

main = do
        fname <- getArgs
        h1 <- openFile (head fname) ReadMode
        list <- hGetContents h1
        putsWCList list
        hClose h1

なるべくポイントフリースタイルになるように頑張ったけど、どうしても、makeWCListの引数の消し方がわからなかった。orz

あと、IOが入ってくると、どうも型がわからなくなってしまう。もっと、修錬をつまねば。

で、実行結果。

$ cat data.txt
hoge haskell ruby ruby moge . hoge
java haskell java
haskell ml ml haskell ruby
$ ./wordcount data.txt
[(4,"haskell"),(3,"ruby"),(2,"ml"),(2,"java"),(2,"hoge"),(1,"moge"),(1,".")]

MarlonMarlon2012/05/03 04:37I could read a book about this without finndig such real-world approaches!

iatyspqozckiatyspqozck2012/05/03 10:518ZSmBT <a href="http://nwuptbxgryod.com/">nwuptbxgryod</a>

enrcjyrcjnwenrcjyrcjnw2012/05/04 10:13rydq6n , [url=http://wbkagxpgncae.com/]wbkagxpgncae[/url], [link=http://zoykzhtkhaas.com/]zoykzhtkhaas[/link], http://mdvxjiudqlsx.com/

kaakujxvqqkaakujxvqq2012/05/05 11:243CpJgr <a href="http://fntjrppotiel.com/">fntjrppotiel</a>

snjyapltizssnjyapltizs2012/05/05 15:11EJVNUh , [url=http://wbguixnczveq.com/]wbguixnczveq[/url], [link=http://cqzgsvhpvrfc.com/]cqzgsvhpvrfc[/link], http://ghrvyaguxrqk.com/

2006-11-05

Haskell日記はじめました 11:29 Haskell日記はじめました - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - Haskell日記はじめました - takkan_mのHaskell再挑戦 Haskell日記はじめました - takkan_mのHaskell再挑戦 のブックマークコメント

最近関数型言語重要性について、話を聞き、感化されたので、またHaskell勉強を再開しました。

とりあえずは、以下のほんの関数型言語の章の問題を解いていきたいと思います。

プログラミング言語の概念と構造

プログラミング言語の概念と構造

リストに関する問題 16:55 リストに関する問題 - takkan_mのHaskell再挑戦 を含むブックマーク はてなブックマーク - リストに関する問題 - takkan_mのHaskell再挑戦 リストに関する問題 - takkan_mのHaskell再挑戦 のブックマークコメント

問題7.1はリストに対する操作の問題。

問題aは、リストから連続する要素の先頭以外を除いたリストを返す関数

list_a [ 1 , 2 , 1 , 1 , 1 , 3 , 3 ]
 => [ 1 , 2 , 1 , 3 ]

問題bは、リストから連続しない要素のみのリストを返す関数

list_a [ 1 , 2 , 1 , 1 , 1 , 3 , 3 ]
 => [ 1 , 2  ]

問題cは、リストから連続する要素のひとつからなるリストを返す関数

list_a [ 1 , 2 , 1 , 1 , 1 , 3 , 3 ]
 => [ 1 , 3  ]

問題dは、リストの要素の繰り替え指数を数えたリストを返す関数

list_a [ 1 , 2 , 1 , 1 , 1 , 3 , 3 ]
 => [ ( 1 , 1) , ( 1 , 2 ) , ( 3 , 1 ) , ( 2 , 3 )  ]

で、実装してみる。各関数コメントに簡単な説明を書いておきます。

-- リストの先頭からxと一致する要素を除いたリストを返す関数
reduce_repeat::(Eq a) => a -> [a] -> [a]
reduce_repeat x [] = []
reduce_repeat x (y:ys) | x /= y = y:ys
		       | x == y = reduce_repeat x ys

--reduce_repeatを使い、先頭要素とreduce_repeatの返すリストのlist_aを連結
list_a::(Eq a) => [a] -> [a]
list_a [] = []
list_a (x:xs) = x : list_a (reduce_repeat x xs)


--先頭と次の要素が等しければ、reduce_repeatの返すリストを
--list_bの適用したリストを返す
--そうでなければ、先頭要素とのこりのリストのlist_bを連結したリストを返す
list_b::(Eq a) => [a] -> [a]
list_b [] = []
list_b (x:xs) = if  length xs == length ( reduce_repeat x xs )
		then x : (list_b xs)
		else list_b (reduce_repeat x xs)


--先頭を除いたリストとreduce_repeatの返すリストが
--等しければその要素とreduce_repeatをlist_cに適用したリストの連結
--そうでなければのこりのリストのlist_cを返す
list_c::(Eq a) => [a] -> [a]
list_c [] = []
list_c (x:xs) = if  length xs == length ( reduce_repeat x xs )
		then list_c xs
		else x : (list_c (reduce_repeat x xs))

--もとのリストとその先頭と残りのリストのreduce_repeatが返すリストの
--個数の差がその要素が連続する個数
list_d::(Eq a) => [a] -> [(Int, a)]
list_d [] = []
list_d (x:xs) = ( (repeat_count x xs),x):( list_d (reduce_repeat x xs))
	where repeat_count x xs = length (x:xs) - length(reduce_repeat x  xs)

ある要素がリストの先頭であるとき、リストの先頭がその要素でなくなるまで、削除したリストを返す関数reduce_repeatを最初に用意。最初は、先頭とその次の要素とその残りのリストとわけてパターンマッチをしていたんだけど、reduce_repeatを用いることで、すっきり書けた気がする。

一回の関数評価で、2度もreduce_repeatをしているので、効率が悪そうな気もするんだけど、Haskellは参照透明性があるから、他の言語にくらべて問題は無いような気がするんだけど実際は、どうなんだろう?特に、list_dとか。

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

   Loading package base-1.0 ... linking ... done.
   Compiling Main             ( func.hs, interpreted )
   Ok, modules loaded: Main.
   *Main> let lists = [ 1 , 2 , 1 , 1 , 1 , 3 , 3 ]
   *Main> list_a lists
   [1,2,1,3]
   *Main> list_b lists
   [1,2]
   *Main> list_c lists
   [1,3]
   *Main> list_d lists
   [(1,1),(1,2),(3,1),(2,3)]

nobsunnobsun2006/11/06 08:11
Haskell 98 標準ライブラリに List というモジュールがあって,そのなかに
group というのが定義されています.参考になると思います.

それを使うと.

list_a :: Eq a => [a] -> [a]
list_a = map head . group
list_b :: Eq a => [a] -> [a]
list_b = map head . filter ((1 ==) . length) . group
list_c :: Eq a => [a] -> [a]
list_c = map head . filter ((1 < ) . length) . group
list_d :: Eq a => [a] -> [(Int,a)]
list_d = map (\ xs -> (length xs, head xs)) . group

とシンプルに定義できます.

takkan_mtakkan_m2006/11/08 00:15隣接する同じ要素をまとめるという関数ですね
めちゃめちゃすっきり書けちゃうんですね。
まだ、自分にはmapという頭がないようです。map使いこなせるようになりたいです