トップページ⇒tech
981コメント365KB

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

レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん2014/07/27(日) 13:46:32.03ID:deqguEnh
関数型プログラミング言語 Haskell について語るスレです。

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

前スレ
関数型プログラミング言語Haskell Part25
http://peace.2ch.net/test/read.cgi/tech/1393313450/
0931デフォルトの名無しさん2015/01/05(月) 13:29:35.01ID:r5Vta5Zs
How to install latest GHC 7.8.3 + cabal 1.20.3 on Ubuntu
https://gist.github.com/yantonov/10083524
0932デフォルトの名無しさん2015/01/05(月) 13:31:02.02ID:PY+NF+zg
>>929
普通は副作用とヌルがあるから IO (Maybe String)
でも普通の常識を疑うためにHaskellやってるんだろ？
0933デフォルトの名無しさん2015/01/05(月) 13:38:45.45ID:rVk7ZNEd
>>929
その方法が一番いい。

1. 素直な方法なので実装しやすくバグが入りにくい。
2. 空リストを考慮しなくてもよく場合分けが必要ない。
3. プログラムソースが見やすく何を求めているのかがよく分かる。
4. 奇数番目だけでなく、x 行おきの場合にも対応でき応用が利く。
0934デフォルトの名無しさん2015/01/05(月) 13:54:22.37ID:UJnBa08N
>>929
リスト走査を1度ですませたいなら融合変換すればよいのでは．
0935デフォルトの名無しさん2015/01/05(月) 13:57:36.10ID:56v1L+Z7
>>932
いやあ，ちょっとした使い捨て的な処理なので，そんなに真面目に例外処理を考えてなかったです

>>933
ひどく効率が悪いとか，そういうことはないんですね
じゃあ初心者としてはわかりやすさ優先でいっときます
なんかこう
s <- getContents
putStr $ unlines $ map fst $ filter (odd . snd) $ zip (lines s) [0..]
みたいな感じで
0936デフォルトの名無しさん2015/01/05(月) 14:03:41.15ID:56v1L+Z7
>>934
融合変換って初めて聞きました
ちょっと勉強してみます
0937デフォルトの名無しさん2015/01/05(月) 14:25:19.60ID:rVk7ZNEd
>>934
>>929 の方法でも走査は一度きりなんだが・・・
0938デフォルトの名無しさん2015/01/05(月) 15:00:51.08ID:1xEaC2gz
>>930
一度も具体的な話が出てこないから、Botだと思いますよ。
0939デフォルトの名無しさん2015/01/05(月) 15:18:52.82ID:r5Vta5Zs
Data.Bits.FiniteBitsありがたや
0940デフォルトの名無しさん2015/01/05(月) 15:18:54.70ID:v9pP0JGy
haskellスレは群雄割拠！原発荒らしやemacs荒らし、上から視線のニートもどき、荒ぶる信者も渾然一体！
0941デフォルトの名無しさん2015/01/05(月) 15:51:07.05ID:OMSF4NSh
>>930
これは同感
エディタとかで最初から最高の環境目指すと考えすぎで止まってしまう
0942デフォルトの名無しさん2015/01/05(月) 15:59:36.20ID:UJnBa08N
>>937
zipで一回，filterで一回，計2回ではないでしょうか？
0943デフォルトの名無しさん2015/01/05(月) 16:26:46.03ID:rVk7ZNEd
>>942
あぁ走査って、リストの要素数 n に対して、
zip の計算量 n、filter の計算量 n とすると、
全体で 2n の計算量になる、と言う意味なのか。
勘違いしてた。

でもそれだと今度は、融合変換しても走査数は変わらないのでは？
融合変換って、中間データ構造（今の問題ならタプル）を消すことでしょ。
0944デフォルトの名無しさん2015/01/05(月) 16:29:22.31ID:UJnBa08N
>>943
中間リストがなくなればその分の走査が減るとおもいます．
0945デフォルトの名無しさん2015/01/05(月) 17:05:16.52ID:4q+Qt2eN
どうもemacsです
アドバイスありがとうございました
0946デフォルトの名無しさん2015/01/05(月) 17:43:05.75ID:rVk7ZNEd
>>944
中間リストって、filter が作る中間リスト？

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

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

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

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

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

走査数の意味がイマイチ分からなくなった。
何を以て走査数と言ってる？
0947デフォルトの名無しさん2015/01/05(月) 18:31:50.63ID:UJnBa08N
>>946
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つ減っていることが期待できますよね．
0948デフォルトの名無しさん2015/01/05(月) 18:48:33.68ID:UJnBa08N
訂正 es → es'
filter' snd (odd . fst) es' は結果のリスト全体を生成するのに es' の全要素を辿ります．
0949デフォルトの名無しさん2015/01/05(月) 18:49:41.11ID:UJnBa08N
中間リストといっているのはzip [0..] が生成するリストのことです．
0950デフォルトの名無しさん2015/01/05(月) 19:20:48.83ID:rVk7ZNEd
>>947
そもそも遅延評価だから、zip に 1回、filter に 1 回というたどり方はしなくて、
走査の定義をハッキリさせておかないと非常にややこしくなるんだが・・・

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

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

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

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

で、俺は走査と言えば、たとえば GCC は C 言語の構文解析を一度スキャン（走査）で行える、
とかいう時のスキャンのイメージがあるから、それなら zip と filter の組み合わせは
リストに対して一度のスキャンで行える、と言ったんだ。
遅延評価だから二度もスキャンする必要はないからね。
0951デフォルトの名無しさん2015/01/05(月) 19:47:30.17ID:UJnBa08N
走査という曖昧な言葉をつかったのが失敗でした．
中間リストの生成を除去するといえばよかったですね．
0952デフォルトの名無しさん2015/01/05(月) 20:19:28.54ID:UJnBa08N
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..]
0953デフォルトの名無しさん2015/01/05(月) 21:13:52.44ID:KI3U0yKn
なにこれ怖い
0954デフォルトの名無しさん2015/01/05(月) 21:34:27.09ID:rVk7ZNEd
>>952
内容は調べていないから融合できているかは知らんが、
何のために融合しようとしているの？
本末転倒になってはいないか？

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

と言っても、かなり大きなリストで試さないと差は見えてこないから、
>>929 の使い方なら実用上どちらを使っても変わらんが。
0955デフォルトの名無しさん2015/01/05(月) 21:49:58.07ID:rVk7ZNEd
>>952
ちなみに、それよりも >>947 の方法の方が速い。

また、ヒープ領域の使用量も速さと同じ結果。
素直に実装した方が少ない使用量で済む。
0956デフォルトの名無しさん2015/01/05(月) 22:23:19.50ID:JId0mbKZ
なんか今の2chってHaslkellで書かれてるらしいじゃん
0957デフォルトの名無しさん2015/01/05(月) 23:47:34.38ID:mLtk6pyN
>>956
マジすか？
0958デフォルトの名無しさん2015/01/06(火) 00:02:57.77ID:WjhpL2zQ
>>954

そもそも，計算量オーダーが同じならコードがわかりにくくなった分，劣化してる可能性大ですねぇ．
0959デフォルトの名無しさん2015/01/06(火) 00:35:30.77ID:WjhpL2zQ
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
0960デフォルトの名無しさん2015/01/06(火) 00:37:44.25ID:WjhpL2zQ
たいした差じゃないともいえるかもしれませんね．
0961デフォルトの名無しさん2015/01/06(火) 00:45:53.98ID:WjhpL2zQ
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,[]))}
0962デフォルトの名無しさん2015/01/06(火) 07:12:15.34ID:1NZMwfJD
>>959
それはなによりです
[0..]とzipしてfilterする方法では回りくどくないかなと心配してた>>929もさぞ喜んでいることでしょう
0963デフォルトの名無しさん2015/01/06(火) 09:21:05.66ID:Ap0lJ8Jt
>>945
haskellでタダシの心と身体を守るんだぞ
0964デフォルトの名無しさん2015/01/06(火) 09:58:56.58ID:iarVVv2t
Haskell って教科書通りの分かりやすいコードを書けば，意外とそれだけでいける場合が有るんだな．
トイコードで書けるような小さいものを相手にしてる場合はいいけど，
データ量が多くなるとすぐにダメになって，参照型とかモナドのオンパレードにしないといけないのかと思ってた．
0965デフォルトの名無しさん2015/01/06(火) 10:00:05.28ID:iarVVv2t
ビックデータと絡めるような試みは有るんかな．調べてみるか．
0966デフォルトの名無しさん2015/01/06(火) 10:29:48.03ID:+nyULczy
http://dev.stephendiehl.com/fun/
0967デフォルトの名無しさん2015/01/06(火) 12:42:53.16ID:4YMDVwAo
リストを扱うならなるべくData.Listの関数を使った方がいい
Rulesプラグマで融合変換して中間リストを除去してるから
自分で再帰を書いたらその部分がボトルネックになる
0968デフォルトの名無しさん2015/01/06(火) 14:31:17.60ID:gN1CYWxI
自分で再帰書いたら中間リストのないコードになるのでは。

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

ところで>>959の差ってどこで生まれてるんだろ？
zip して filter は素のリストだと融合変換してくれないの？
unlines のところの中間リストの違い？
http://hackage.haskell.org/package/stream-fusion-0.1.1/docs/Data-List-Stream.html
とかを使うと変わるかな？
0969デフォルトの名無しさん2015/01/06(火) 17:57:28.03ID:1NZMwfJD
>>968
filter が優良生産者として実装されているから、
同じく優良生産者として機能しているときの zip に続けても融合されない、
ということでは？
http://www.kotha.net/ghcguide_ja/latest/rewrite-rules.html#idm140193846702112
0970デフォルトの名無しさん2015/01/06(火) 19:30:02.76ID:gN1CYWxI
>>967
ああ、他の Data.List 関数と一緒に使うならそうか。

>>969
ソース読めって書いてあるとおり読んでみると、
build を使ってれば優良生産者で foldr を使っていると優良消費者で、
両者になるのは同時に可能ってことだと思うんだけど。
0971デフォルトの名無しさん2015/01/06(火) 20:06:42.53ID:NJ/kfRzj
>>959のコードと普通に書いたコードの速度比較した

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

(1) >>959のコード1つ目 : http://codepad.org/Guy2CswB
(2) >>959のコード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)

>>967で書いた通り、自分で書いた再帰を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)
0972デフォルトの名無しさん2015/01/06(火) 20:43:09.13ID:gN1CYWxI
ああ、filter' というのを使ってたんだ。
融合変換はちゃんとされてると。
でも差は意外と無かった？
0973デフォルトの名無しさん2015/01/06(火) 21:27:05.66ID:1NZMwfJD
>>970
ごめん、自分でリンク貼っておいて見落としてた。

filterは優良生産者であると同時に優良消費者でもあった。
0974デフォルトの名無しさん2015/01/06(火) 21:35:49.65ID:1NZMwfJD
>>972
融合変換と言っても、トイプログラムや日常のちょとしたスクリプト程度ではあまり意味ないかもね。
Repaみたいな、ああいったもので本当に活きてくる、というかなくてはならない存在だと思う。
0975デフォルトの名無しさん2015/01/06(火) 21:52:22.72ID:0YpM91P0
needleってなんだよ！　ふざけてんのか！
0976デフォルトの名無しさん2015/01/06(火) 22:06:08.57ID:WLnq9lHu
尖ってんだよ
0977デフォルトの名無しさん2015/01/06(火) 22:08:58.99ID:1NZMwfJD
>>975
全く役にはたたんが、こういう発想ステキ
0978デフォルトの名無しさん2015/01/07(水) 07:46:09.67ID:gDzpAQ9k
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
0979デフォルトの名無しさん2015/01/07(水) 07:46:43.21ID:gDzpAQ9k
>>978のつづき

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}
0980デフォルトの名無しさん2015/01/07(水) 10:16:03.90ID:gDzpAQ9k
>>978-979 のLambda pastebinです。
http://lpaste.net/117957
0981デフォルトの名無しさん2015/01/07(水) 18:26:38.49ID:ia1dpi4p
オライリーの表紙がカブトムシなのは何でなんだ?
perlのラクダ、pythonの蛇のようにマスコット?
レス数が950を超えています。1000を超えると書き込みができなくなります。