関数型プログラミング言語Haskell Part26

1 ：デフォルトの名無しさん：2014/07/27(日) 13:46:32.03 ID:deqguEnh.net

関数型プログラミング言語 Haskell について語るスレです。

haskell.org (公式サイト)
http://www.haskell.org/

前スレ
関数型プログラミング言語Haskell Part25
http://peace.2ch.net/test/read.cgi/tech/1393313450/

936 ：デフォルトの名無しさん：2015/01/05(月) 13:38:45.45 ID:rVk7ZNEd.net

>>932
その方法が一番いい。

1. 素直な方法なので実装しやすくバグが入りにくい。
2. 空リストを考慮しなくてもよく場合分けが必要ない。
3. プログラムソースが見やすく何を求めているのかがよく分かる。
4. 奇数番目だけでなく、x 行おきの場合にも対応でき応用が利く。

937 ：デフォルトの名無しさん：2015/01/05(月) 13:54:22.37 ID:UJnBa08N.net

>>932
リスト走査を1度ですませたいなら融合変換すればよいのでは．

938 ：デフォルトの名無しさん：2015/01/05(月) 13:57:36.10 ID:56v1L+Z7.net

>>935
いやあ，ちょっとした使い捨て的な処理なので，そんなに真面目に例外処理を考えてなかったです

>>936
ひどく効率が悪いとか，そういうことはないんですね
じゃあ初心者としてはわかりやすさ優先でいっときます
なんかこう
s <- getContents
putStr $ unlines $ map fst $ filter (odd . snd) $ zip (lines s) [0..]
みたいな感じで

939 ：デフォルトの名無しさん：2015/01/05(月) 14:03:41.15 ID:56v1L+Z7.net

>>937
融合変換って初めて聞きました
ちょっと勉強してみます

940 ：デフォルトの名無しさん：2015/01/05(月) 14:25:19.60 ID:rVk7ZNEd.net

>>937
>>932 の方法でも走査は一度きりなんだが・・・

941 ：デフォルトの名無しさん：2015/01/05(月) 15:00:51.08 ID:1xEaC2gz.net

>>933
一度も具体的な話が出てこないから、Botだと思いますよ。

942 ：デフォルトの名無しさん：2015/01/05(月) 15:18:52.82 ID:r5Vta5Zs.net

Data.Bits.FiniteBitsありがたや

943 ：デフォルトの名無しさん：2015/01/05(月) 15:18:54.70 ID:v9pP0JGy.net

haskellスレは群雄割拠！原発荒らしやemacs荒らし、上から視線のニートもどき、荒ぶる信者も渾然一体！

944 ：デフォルトの名無しさん：2015/01/05(月) 15:51:07.05 ID:OMSF4NSh.net

>>933
これは同感
エディタとかで最初から最高の環境目指すと考えすぎで止まってしまう

945 ：デフォルトの名無しさん：2015/01/05(月) 15:59:36.20 ID:UJnBa08N.net

>>940
zipで一回，filterで一回，計2回ではないでしょうか？

946 ：デフォルトの名無しさん：2015/01/05(月) 16:26:46.03 ID:rVk7ZNEd.net

>>945
あぁ走査って、リストの要素数 n に対して、
zip の計算量 n、filter の計算量 n とすると、
全体で 2n の計算量になる、と言う意味なのか。
勘違いしてた。

でもそれだと今度は、融合変換しても走査数は変わらないのでは？
融合変換って、中間データ構造（今の問題ならタプル）を消すことでしょ。

947 ：デフォルトの名無しさん：2015/01/05(月) 16:29:22.31 ID:UJnBa08N.net

>>946
中間リストがなくなればその分の走査が減るとおもいます．

948 ：デフォルトの名無しさん：2015/01/05(月) 17:05:16.52 ID:4q+Qt2eN.net

どうもemacsです
アドバイスありがとうございました

949 ：デフォルトの名無しさん：2015/01/05(月) 17:43:05.75 ID:rVk7ZNEd.net

>>947
中間リストって、filter が作る中間リスト？

zip が作る [(String, Int)] に対して「ひとつおきに取り出す処理」は、
あなたの言う走査には含まれない？

融合変換で中間リストが消えて走査数が減ると言うのなら、元々の操作数は、

1. zip が引数のリストを分解する
2. zip がリストを作る
3. filter がリストを分解する
4. filter がリストを作る

の 4 つで、そのうち 2 と 3 が消えて 2つになるのでは？

あるいは、zip は「2つのリスト」に対して処理するから、
元々の走査数は zip 2、filter 1 で計 3 つになるとか？

走査数の意味がイマイチ分からなくなった。
何を以て走査数と言ってる？

950 ：デフォルトの名無しさん：2015/01/05(月) 18:31:50.63 ID:UJnBa08N.net

>>949
oddElems :: [a] -> [a]
oddElems = filter' snd (odd . fst) . zip [0..]
filter' _ _ [] = []
filter' f p (x:xs) = if p x then f x : filter' f p xs
このとき，oddElem の入力となるリストを es．その長さを n = length es とします．
zip [0..] は関数で，この関数が結果のリスト全体を作成するには es の全要素を辿ります.
zip [0..] es が生成するリストを es' とすると，そのは長さは es の長さと同じ n です．
filter' snd (odd . fst) es' は結果のリスト全体を生成するのに es の全要素を辿ります．
融合変換して es' という中間リストがなくなれば，辿るべきリストが1つ減っていることが期待できますよね．

951 ：デフォルトの名無しさん：2015/01/05(月) 18:48:33.68 ID:UJnBa08N.net

訂正 es → es'
filter' snd (odd . fst) es' は結果のリスト全体を生成するのに es' の全要素を辿ります．

952 ：デフォルトの名無しさん：2015/01/05(月) 18:49:41.11 ID:UJnBa08N.net

中間リストといっているのはzip [0..] が生成するリストのことです．

953 ：デフォルトの名無しさん：2015/01/05(月) 19:20:48.83 ID:rVk7ZNEd.net

>>950
そもそも遅延評価だから、zip に 1回、filter に 1 回というたどり方はしなくて、
走査の定義をハッキリさせておかないと非常にややこしくなるんだが・・・

リストに対する融合で消えるのはあくまで、
「リストの作成」とその直後の「リストの分解」という一対の処理だけだよ。

zip が行う「タプルを作る処理」や filter が行う「奇数番目かどうか判定する処理」は消えない。
この 2 つの処理が全体で何回行われるかというと、融合されようが、されまいが、
きっちり最初に zip に渡されたリストの要素数分だ。
減りも増えもしない。
（正確には、結果のリストをどう評価するかによるが）

融合によってリストの作成分解処理が一対消えるから、
この処理のことを走査と言うのなら確かに走査数は減ることになる。

タプルの作成や奇数判定も走査の中に含めるのなら、走査数は変わらんよ。

で、俺は走査と言えば、たとえば GCC は C 言語の構文解析を一度スキャン（走査）で行える、
とかいう時のスキャンのイメージがあるから、それなら zip と filter の組み合わせは
リストに対して一度のスキャンで行える、と言ったんだ。
遅延評価だから二度もスキャンする必要はないからね。

954 ：デフォルトの名無しさん：2015/01/05(月) 19:47:30.17 ID:UJnBa08N.net

走査という曖昧な言葉をつかったのが失敗でした．
中間リストの生成を除去するといえばよかったですね．

955 ：デフォルトの名無しさん：2015/01/05(月) 20:19:28.54 ID:UJnBa08N.net

oddElems :: [a] -> [a]
oddElems = filter' snd (odd . fst) . zip [0..]

filter' snd (odd . fst) . zip [0..]
⇔ { zipp = uncurry zip とする }
filter' snd (odd . fst) . zipp . (,) [0..]
⇔ { addifodd (i,x) xs = if odd i then x:xs eles xs とする }
foldr addifodd [] . zipp . (,) [0..]
⇔ { phipair (xxs,yys) = if null xxs || null yys then Nothing else Just ((head xxs,head yys),(tail xxs, tail yys)) とする }
foldr addifodd [] . unfoldr phipair . (,) [0..]
⇔ { hylo f e phi x = case phi x of {Nothing -> e; Just (y,z) -> f y (hylo f e phi z)} とする }
hylo addifodd [] phipair . (,) [0..]

まちがえてなければ，これで融合変換できたことになると思います．
oddelems = hylo addifodd [] phipair . (,) [0..]

956 ：デフォルトの名無しさん：2015/01/05(月) 21:13:52.44 ID:KI3U0yKn.net

なにこれ怖い

957 ：デフォルトの名無しさん：2015/01/05(月) 21:34:27.09 ID:rVk7ZNEd.net

>>955
内容は調べていないから融合できているかは知らんが、
何のために融合しようとしているの？
本末転倒になってはいないか？

適当なテストプログラムを書いてコンパイルし、
RTS オプション の -s を付けて実行して処理時間を測ってみ。
素直に filter と zip を使った方が速いから。

と言っても、かなり大きなリストで試さないと差は見えてこないから、
>>932 の使い方なら実用上どちらを使っても変わらんが。

958 ：デフォルトの名無しさん：2015/01/05(月) 21:49:58.07 ID:rVk7ZNEd.net

>>955
ちなみに、それよりも >>950 の方法の方が速い。

また、ヒープ領域の使用量も速さと同じ結果。
素直に実装した方が少ない使用量で済む。

959 ：デフォルトの名無しさん：2015/01/05(月) 22:23:19.50 ID:JId0mbKZ.net

なんか今の2chってHaslkellで書かれてるらしいじゃん

960 ：デフォルトの名無しさん：2015/01/05(月) 23:47:34.38 ID:mLtk6pyN.net

>>959
マジすか？

961 ：デフォルトの名無しさん：2015/01/06(火) 00:02:57.77 ID:WjhpL2zQ.net

>>957

そもそも，計算量オーダーが同じならコードがわかりにくくなった分，劣化してる可能性大ですねぇ．

962 ：デフォルトの名無しさん：2015/01/06(火) 00:35:30.77 ID:WjhpL2zQ.net

interact (show . length . unlines . oddelems . lines)
の処理と unlines . oddelems . lines の部分を融合変換したもの
interact (show . length . hylo addifodd "" numlines)
の処理とを比較してみました．63469440行ある単語データファイル(600MB)を食わせてみたところ
手元の計算機でかかった時間は以下の結果
前者はTotal time 33.59s ( 34.20s elapsed) %GC time 14.6% (24.5% elapsed)
後者はTotal time 27.87s ( 28.38s elapsed) %GC time 7.5% (19.7% elapsed)
IO部分の時間を図ってないのでなんともいえないですが，この場合は差がでるようにみえますね．
コンパイルオプション-O2

963 ：デフォルトの名無しさん：2015/01/06(火) 00:37:44.25 ID:WjhpL2zQ.net

たいした差じゃないともいえるかもしれませんね．

964 ：デフォルトの名無しさん：2015/01/06(火) 00:45:53.98 ID:WjhpL2zQ.net

1つめの処理の oddelems は oddElems のまちがい．
2つめの処理は
interact (show . length . hylo addifodd "" numlines . (,) [0..])
のまちがい．

numlines (_,[]) = Nothing
numlines (i:is,xs) = case break ('\n'==) xs of {
(ys,_:zs) -> Just ((i,ys),(is,zs));
(ys,[]) -> Just ((i,ys),(is,[]))}

965 ：デフォルトの名無しさん：2015/01/06(火) 07:12:15.34 ID:1NZMwfJD.net

>>962
それはなによりです
[0..]とzipしてfilterする方法では回りくどくないかなと心配してた>>932もさぞ喜んでいることでしょう

966 ：デフォルトの名無しさん：2015/01/06(火) 09:21:05.66 ID:Ap0lJ8Jt.net

>>948
haskellでタダシの心と身体を守るんだぞ

967 ：デフォルトの名無しさん：2015/01/06(火) 09:58:56.58 ID:iarVVv2t.net

Haskell って教科書通りの分かりやすいコードを書けば，意外とそれだけでいける場合が有るんだな．
トイコードで書けるような小さいものを相手にしてる場合はいいけど，
データ量が多くなるとすぐにダメになって，参照型とかモナドのオンパレードにしないといけないのかと思ってた．

968 ：デフォルトの名無しさん：2015/01/06(火) 10:00:05.28 ID:iarVVv2t.net

ビックデータと絡めるような試みは有るんかな．調べてみるか．

969 ：デフォルトの名無しさん：2015/01/06(火) 10:29:48.03 ID:+nyULczy.net

http://dev.stephendiehl.com/fun/

970 ：デフォルトの名無しさん：2015/01/06(火) 12:42:53.16 ID:4YMDVwAo.net

リストを扱うならなるべくData.Listの関数を使った方がいい
Rulesプラグマで融合変換して中間リストを除去してるから
自分で再帰を書いたらその部分がボトルネックになる

971 ：デフォルトの名無しさん：2015/01/06(火) 14:31:17.60 ID:gN1CYWxI.net

自分で再帰書いたら中間リストのないコードになるのでは。

まあ融合変換は現実的には自分の手でやるもんじゃないよね。

ところで>>962の差ってどこで生まれてるんだろ？
zip して filter は素のリストだと融合変換してくれないの？
unlines のところの中間リストの違い？
http://hackage.haskell.org/package/stream-fusion-0.1.1/docs/Data-List-Stream.html
とかを使うと変わるかな？

972 ：デフォルトの名無しさん：2015/01/06(火) 17:57:28.03 ID:1NZMwfJD.net

>>971
filter が優良生産者として実装されているから、
同じく優良生産者として機能しているときの zip に続けても融合されない、
ということでは？
http://www.kotha.net/ghcguide_ja/latest/rewrite-rules.html#idm140193846702112

973 ：デフォルトの名無しさん：2015/01/06(火) 19:30:02.76 ID:gN1CYWxI.net

>>970
ああ、他の Data.List 関数と一緒に使うならそうか。

>>972
ソース読めって書いてあるとおり読んでみると、
build を使ってれば優良生産者で foldr を使っていると優良消費者で、
両者になるのは同時に可能ってことだと思うんだけど。

974 ：デフォルトの名無しさん：2015/01/06(火) 20:06:42.53 ID:NJ/kfRzj.net

>>962のコードと普通に書いたコードの速度比較した

テストデータの生成に使ったコード: http://codepad.org/2Qljhutm

(1) >>962のコード1つ目 : http://codepad.org/Guy2CswB
(2) >>962のコード2つ目 : http://codepad.org/S3DdUiGL
(3) 素直にData.Listの関数だけで書く : http://codepad.org/7SZtvyJ9

実行結果
　(1) Total time 25.02s (25.65s elapsed) %GC time 19.9% (19.8% elapsed)
　(2) Total time 23.05s (23.62s elapsed) %GC time 22.0% (21.8% elapsed)
　(3) Total time 24.45s (25.06s elapsed) %GC time 20.3% (20.4% elapsed)

>>970で書いた通り、自分で書いた再帰をData.Listの関数と一緒に使うと遅くなる
ほとんど差は無いので手で融合変換する手間を考えたら素直にData.Listの関数だけで書いた方がマシ


以下はおまけ
　(4) Text + ByteString : http://codepad.org/WcNZH4zD
　(5) Text + ByteString + Vector : http://codepad.org/5lAwD8PI

実行結果
　(4) Total time 13.61s (14.18s elapsed) %GC time 2.9% (3.4% elapsed)
　(5) Total time 2.21s ( 2.68s elapsed) %GC time 2.2% (2.2% elapsed)

975 ：デフォルトの名無しさん：2015/01/06(火) 20:43:09.13 ID:gN1CYWxI.net

ああ、filter' というのを使ってたんだ。
融合変換はちゃんとされてると。
でも差は意外と無かった？

976 ：デフォルトの名無しさん：2015/01/06(火) 21:27:05.66 ID:1NZMwfJD.net

>>973
ごめん、自分でリンク貼っておいて見落としてた。

filterは優良生産者であると同時に優良消費者でもあった。

977 ：デフォルトの名無しさん：2015/01/06(火) 21:35:49.65 ID:1NZMwfJD.net

>>975
融合変換と言っても、トイプログラムや日常のちょとしたスクリプト程度ではあまり意味ないかもね。
Repaみたいな、ああいったもので本当に活きてくる、というかなくてはならない存在だと思う。

978 ：デフォルトの名無しさん：2015/01/06(火) 21:52:22.72 ID:0YpM91P0.net

needleってなんだよ！　ふざけてんのか！

979 ：デフォルトの名無しさん：2015/01/06(火) 22:06:08.57 ID:WLnq9lHu.net

尖ってんだよ

980 ：デフォルトの名無しさん：2015/01/06(火) 22:08:58.99 ID:1NZMwfJD.net

>>978
全く役にはたたんが、こういう発想ステキ

981 ：デフォルトの名無しさん：2015/01/07(水) 07:46:09.67 ID:gDzpAQ9k.net

Control.Lensで指定したビットフィールドを取り出す演算子(.#.)をつくったところ
"bfget"の型がどうなっているのかわからなくなってしまいました。
お知恵をお借りしたく... (ghc version 7.6.3, lens-4.3.3)
--------------------
{-# LANGUAGE TemplateHaskell #-}
module A where

import Control.Lens (ALens',makeLenses,cloneLens,lens,to,(.~),(%~),(&),(^.))
import Data.Word (Word32,Word64)
import Data.Bits (Bits,FiniteBits,complement,shiftL,shiftR,rotateL,(.|.),(.&.))
import Test.HUnit (Test,test,runTestTT,(~=?))

data Regs = Regs { _r0 :: Word32, _r1 :: Word64 } deriving (Show, Eq)
$(makeLenses ''Regs)

(.#.) :: (Functor f, FiniteBits a, Bounded a, Integral a) =>
ALens' Regs a -> (Int, Int) -> ((a -> f a) -> Regs -> f Regs)
(.#.) r (lsb, nbits) = let
-- ??? bfget :: Integral a => Regs -> a
bfget rs = rs ^. (cloneLens r) . to (flip shiftR lsb . (.&. complement mask))
bfset :: Integral a => Regs -> a -> Regs
bfset rs x = rs & (cloneLens r) %~ \ w -> (mask .&. w) .|. (complement mask .&. shiftL (fromIntegral x) lsb)
mask :: (Bits a, Bounded a) => a
mask = flip rotateL lsb $ shiftL maxBound nbits
in lens bfget bfset

982 ：デフォルトの名無しさん：2015/01/07(水) 07:46:43.21 ID:gDzpAQ9k.net

>>981のつづき

main = runTestTT $ test [
(rs & r0 .#. (4,16) .~ 0xcafe) ^. r0 .#. (4,16) ~=? 0xcafe
, (rs & r0 .#. (8,24) .~ (rs ^. r0 .#. (8,24))) ~=? rs
, ((rs & r0 .#. (0,32) .~ 0xabadcafe) & r0 .#. (0,32) .~ 0xdeadbeaf) ~=? rs {_r0=0xdeadbeaf}
, (rs & r1 .#. (4,16) .~ 0xcafe) ^. r1 .#. (4,16) ~=? 0xcafe
, (rs & r1 .#. (8,24) .~ (rs ^. r1 .#. (8,24))) ~=? rs
, ((rs & r1 .#. (0,64) .~ 0xabadcafe) & r1 .#. (0,64) .~ 0xdeadbeaf) ~=? rs {_r1=0xdeadbeaf}
]
where rs = Regs {_r0 = 0x01234567,_r1=0x0123456789abcdef}

983 ：デフォルトの名無しさん：2015/01/07(水) 10:16:03.90 ID:gDzpAQ9k.net

>>981-982 のLambda pastebinです。
http://lpaste.net/117957

984 ：デフォルトの名無しさん：2015/01/07(水) 18:26:38.49 ID:ia1dpi4p.net

オライリーの表紙がカブトムシなのは何でなんだ?
perlのラクダ、pythonの蛇のようにマスコット?

985 ：デフォルトの名無しさん：2015/07/20(月) 11:59:41.38 ID:Pp+qjErGv

Leksah を導入しようとしてるんだが読み仮名振るとしたらどう読めばいいんだろうか？