GHCでUNIQ
一つ違いzipによるuniq
まあ、昨日のscheme版の焼き直し。haskellの方が読みやすいが数字しかuniq出来ない
あと、メタな記号が入れられないので(今回は1000でごまかした)いまいち。
Prelude> (\x->reverse $ drop 1 $ reverse $fst $ unzip $ filter (\x->(fst x)/=(snd x)) $ zip (x++[1000]) ([1000]++x)) [1,1,2,2,3,3,3,2,2,4] [1,2,3,2,4]
追記:Maybeモナドを使う場面だそうです。
Prelude Maybe> (\x->catMaybes$fst$unzip$filter (\x->fst x/=snd x)$zip ((map Just x)++[Nothing]) ([Nothing]++(map Just x))) [1,1,2,2,3,3,3,3,2,2,4] [1,2,3,2,4]
ちょっと忘れてるのでもう少し書いておく
Prelude List> :m Maybe Prelude Maybe> map Just [1,2,3] [Just 1,Just 2,Just 3] Prelude Maybe> catMaybes $ map Just [1,2,3] [1,2,3]
Justとか最初の勉強以来だ catMaybesもあんまつかわんし。
でもこれのおかげで Nothing->"" ってのがかっこいい、まるで虚数のようだ
foldrを使ったuniq
やっぱ引数の処理はhaskellがかっこいいな。有無を言わさずカリー化(?)されるのはすごい。schemeだともう一つlambdaが必要だもんな。
まあ、haskellの場合 foo=がdefine foo (lambda (x) まで担当してるんだろうな。
Prelude> let uniq = foldr (\x y->if y==[]||x/=(head y) then [x]++y else y) [] Prelude> uniq [1,1,2,2,3,3,3,2,4,4] [1,2,3,2,4]
groupを用いたuniq
コメントでおしえてもらったやつ。数字だけじゃないところがいい。
これは以前知っていたような気がするんだがgroupの存在を完全に忘れてました。
Prelude Maybe> :m List Prelude List> let uniq1 xs = map head $ group xs Prelude List> uniq1 ["b","c","a","a","d","c"] ["b","c","a","d","c"] Prelude List> uniq1 [1,2,2,3,3,3,2,4,4] [1,2,3,2,4]
Gaucheのutil.matchを勉強してみる
とりあえずはこんなかんじらしい
>> (match '(1 2 3) ((a b c) (list a b c))) => (1 2 3) >> (match '(1 (2 3)) ((a (b c)) (list a b c))) => (1 2 3)
つぎに、リスト処理させてみる
>>(match '(1 2 3 4) ((x . xs) (print x))) 1 =>#<undef> >>(match '(1 2 3 4) ((x . xs) (print xs))) (2 3 4)
なるほど。こりゃおもしろい。
>>((match-lambda ((x . xs) xs)) '(1 2 3 4)) =>(2 3 4)
おお、括弧がひとつ削れるのか。
>>((lambda (a) (match a ((x . xs) xs))) '(1 2 3 4)) =>(2 3 4)
こいつと同じと。確かに短くなってる(笑
で、変なのがあったのでそいつを実験
>>(match-lambda (() '())) =>#<closure #f> >>(lambda (x) (match x (() '()))) =>#<closure #f> >>((lambda (x) (match x (() '()))) ()) =>()
なるほどー。すごいなこりゃ。
並列で書いてあるのでそこを実験
>>((match-lambda (() "null") ((x . xs) xs)) ()) =>null >>((match-lambda (() "null") ((x . xs) xs)) '(1 2 3)) =>(2 3)
おお、null?時のifを一つ省略できる。
ってことで、match-lambdaを使ってクイックソートを書き直してみた
>>(define qsort (match-lambda (()()) ((x . xs) (receive (l r) (partition (lambda (y) (< y x)) xs) (append (qsort l) (list x) (qsort r)))))) =>qsort >>(qsort '(4 3 5 2 5 2 3 4)) =>(2 2 3 3 4 4 5 5)
よし。後はcutと準クオートだ。
ifがなくなるのは良い記法だなー
以下のように木構造をきれいに辿れるらしい。
(define (walk func tree) (match tree [() '()] [(x . xs) `(,(walk func x) . ,(walk func xs))] [x (func x)] )) -->walk (walk (lambda (x) (+ x 1)) '(1 2 (3 4 (5)) 6)) -->(2 3 (4 5 (6)) 7)
Gaucheで多値を扱う。
filterとremoveを同時にやるpartitionを教えてもらったので使ってみようと思ったらなんと多値じゃないか。
なになに?参照渡しがどうのこうの・・・って schemeは参照渡しだよな。
>>(let ((a '(1 2 3))) (print a)((lambda (x) (filter! odd? x)) a) a) (1 2 3) =>(1 3)
なんかよくわからないが とりあえず、ここで中断する。
>>(receive (a b)(values 1 2)(list a b)) =>(1 2)
ここでreceive句がbegin句と大体同じ機能を持ってることがわかったので良しとしよう。
call/ccは先のばし。メリットがわからないんだもん。
Gaucheのpartitionでqsort
多値を使ったpartitionでqsortをしてみる
>>(define qsort (lambda (x) (if (null? x) () (receive (l r) (partition (lambda (y) (< y (car x))) (cdr x)) (append (qsort l) (list (car x)) (qsort r)))))) =>qsort >>(qsort '(5 3 4 2 3)) =>(2 3 3 4 5)
receive句をbegin句と同様に扱えば別に怖くないことが判明。
準クオート
しょうがないやるか。
>>(let ((x '(1 2 3 4))) `(a x c d)) =>(a x c d) >>(let ((x '(1 2 3 4))) `(a ,x c d)) =>(a (1 2 3 4) c d) >>(let ((x '(1 2 3 4))) `(a ,@x c d)) =>(a 1 2 3 4 c d) >>(let ((x 2)) `(a ,x c d)) =>(a 2 c d) >>(let ((x 2)) `(1 2 ,(+ x 1) 4)) =>(1 2 3 4) >>(let ((x 1)) `,x) =>1
なるほど!S式版の文字列展開みたいなもんか。R5RSにものってたのか。丸々無視してた。
念願のconsの逆もかけるんだ。
>>(let ((x '(1 2 3)) (y 4)) `(,@x ,y)) =>(1 2 3 4) >>(let ((x '(1 2 3)) (y 4)) (cons y x)) =>(4 1 2 3)
ほんとはpushみたいな関数あるのかもしれないけど今のところ発見できない。
というわけでいままでの知識を元にクイックソートを書き直した
>>(define qsort (match-lambda (()()) ((x . xs) (receive (l r) (partition (lambda (y) (< y x)) xs) `(,@(qsort l) ,x ,@(qsort r)))))) =>qsort >>(qsort '(4 3 5 2 5 2 3 4)) =>(2 2 3 3 4 4 5 5)
rubyでクイックソートを書いてみる。
そういえば今までrubyでは .sortをつかって知らない振りをしていたんだがrubyで書くとどうなるかやってみる。
>> def qsort(x) x.size<2?x:(y=x.shift;z=x.partition{|i|i<y};[qsort(z[0]),y,qsort(z[1])]) end => nil >> qsort([3,4,5,1,1,2]) => [[[], 1, [[], 1, [2]]], 3, [[], 4, [5]]] >> def qsort(x) x.size<2?x:(y=x.shift;z=x.partition{|i|i<y};[qsort(z[0]),y,qsort(z[1])].flatten) end => nil >> qsort([3,4,5,1,1,2]) => [1, 1, 2, 3, 4, 5]
flattenがずるいと感じるのは、間違いなくだんだんscheme脳になってきたんじゃないかな?(笑)
ghci中でモジュールをインポートする
いつも忘れてしまうのでメモする importをghci中で用いるには
:mをつかう。
Prelude> :m List Prelude List>
あと hugsでは whereだが、 ghciではlet
Gaucheでuniq(そろそろやめよう)
なんてことだ。gauche.sequence の group-sequenceがhaskellのgroupと同じだとは
>>(use gauche.sequence) =>#<undef> >>(group-sequence '(1 1 2 3 3 2 2 4)) =>((1 1) (2) (3 3) (2 2) (4)) >>(map car (group-sequence '(1 1 2 3 3 2 2 4))) =>(1 2 3 2 4)
あと、gauche.collectionもおもしろそう。
>>(group-collection '(1 1 4 4 2 3 3 2 2 4)) =>((1 1) (4 4 4) (2 2 2) (3 3))
sort+uniqみたいなもんね。まあ、並び替えはしないけど。