haskell-jp / questions #67

一応補足ですが，現在の GHC では full laziness が入るタイミングが調整されていて，

factMemo :: Int -> Integer
factMemo = (map fact' [0..] !!)
  where
    fact' 0 = 1
    fact' n = fromIntegral n * factMemo (n - 1)

fact :: Int -> Integer
fact x = map fact' [0..] !! x
  where
    fact' 0 = 1
    fact' n = fromIntegral n * fact (n - 1)

はどちらも fact' は外に出されます．このため， map fact' [0..] も CAF として扱われます． GHCi のバイトコード出すパスでは， core 2 core のパスが少し簡略化されてるので， full laziness が真面目に入ってないだけだと思いますね．

なので，スーパーコンビネータかどうかは指標の一つではありますが，実際にはどう最適化が入るかによって CAF になるかはかなり左右されます

@Mokumitsu has joined the channel

@Cynthia has joined the channel

Liquid Haskell について言えば、`{-@ @-}` は GHC にとっては単なるコメントなのでもっと早い段階で消えそう……な気がしますが根拠はないです。

確かに あれはただのコメントでプラグまですらなかったですね:persevere: 雰囲気的に(?) 型が削除される以前に消されてそうですね…

はい、”外に出す”ということをコンパイラがやるかどうかはまた別ですもんね.

真面目に入ってない

ただ後者のfact’がxを巻き込まずに外に出せるとすると意味論的に変わっちゃわないのかなという疑問が湧いてきたんだけど…

@miau has joined the channel

@mazamachi has joined the channel

GHC の最適化は通常 equational reasoning に基づいて行われてるので，その意味で意味論が変わるものはあまりないと思いますね (Haskell はちゃんとした formal semantics はないので，ある程度簡略化したラムダ計算の体系の元でということにはなりますが)．

CAF を static closure にして欲しくないという話であれば， https://stackoverflow.com/questions/6090932/how-to-make-a-caf-not-a-caf-in-haskell/6091166#6091166 みたいな話があって，今回の場合 map fact' [0..] の部分を切り出して， fact の引数を受け取るようにして NOINLINE すればいいと思いますね．と，思ったんですが，

fact2 :: Int -> Integer
fact2 x = factMemo2 x fact' !! x
  where
    fact' 0 = 1
    fact' n = fromIntegral n * fact' (n - 1)

factMemo2 :: Int -> (Int -> Integer) -> [Integer]
factMemo2 _ f = map f [0..]
{-# NOINLINE factMemo2 #-}

みたいなのだと， w/w が入って factMemo2 の参照が worker の方に書き換えられてしまいますね… 一応次の形式にすると -O ならいい感じに CAF 化を妨害できるみたいです:

fact2 :: Int -> Integer
fact2 x = factMemo2 (x < 0) fact' !! x
  where
    fact' 0 = 1
    fact' n = fromIntegral n * fact' (n - 1)

factMemo2 :: Bool -> (Int -> Integer) -> [Integer]
factMemo2 !_ f = map f [0..]
{-# NOINLINE factMemo2 #-}

@tamuhey has joined the channel

みなさんHTMLを出力するときに、どんなテンプレートエンジンを使っていますか？
こちらのissue https://github.com/haskell-jp/slack-log/issues/20 に取り組む際の参考にしようと思います。

楽なんで Mustache です :raising_hand: （型の活用はあんまりできないやつですが）
http://hackage.haskell.org/package/stache

blaze-htmlとか使うからテンプレートエンジン使いません！だと今回のケースはちょっとつらい。
ユーザーがカスタマイズできるように外部のテンプレートエンジンを使おう、という趣旨なので

Mustacheやっぱ定番ですかね。
ユーザーがカスタマイズするという要件なので型が緩いのはこの際気にしません！ :muscle:
起動時にテンプレートをコンパイルしてチェックする、みたいな考慮は必要でしょうね... mustacheならそれもできたはず。

@ has joined the channel

blaze-html はテンプレートエンジンとはまた違うか :tashikani:

関連議論を全部は追い切れていないのですが、再コンパイルが問題であるなら、現状の仕組みをrunghcで動かすのはどうでしょうか？

Dhallもテンプレートエンジンとして使える事を謳っているのですが、現状パフォーマンスがすこぶる悪いのが難点です http://www.haskellforall.com/2017/06/dhall-is-now-template-engine.html

我々だけでなく、ほかのSlack Workspaceの管理者も使えるように、実行ファイルのリリースも視野に入れているので、runghcだとちとつらいですね...
https://github.com/haskell-jp/slack-log/issues/22

https://qiita.com/autotaker1984/items/5ec0bbd5a44e146dbada を読んでいて気になったのですが、
リストリテラル [1, 2, 3] が build (\c n -> c 1 (c 2 (c 3 n))) に変換されるというルールはどこに載っているでしょうか？
baseパッケージのGHC.List moduleやGHC.Base moduleを探してみましたが見つかりませんでした。
きっとコンパイラーのどこかの層に組み込まれているから、librariesの方を見てもわからないってことですよね...

一応 https://gitlab.haskell.org/ghc/ghc/blob/ghc-8.6.5-release/compiler/deSugar/DsExpr.hs#L837 の部分がそうです。リテラルは Haskell レベルだといじれないので通常は脱糖で扱われることになりますね

リスト、木、グラフみたいな基本的なデータ構造のうえでの、ソートとか探索とかの基本的なアルゴリズムについて Haskell でのコードをまとめたサイトとか本はなにかありますか？

ぱっと思いつくのは https://scrapbox.io/haskell-shoen/%E3%83%AC%E3%82%B7%E3%83%94%E9%9B%86 と https://wiki.haskell.jp/%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E5%88%97%E4%BC%9D ですが、前者は建設中っぽいし後者はデータ構造そのものの紹介で操作については言及してないしなぁ...

ありがとうございます！

なかなかまとまってる資料が見当たらず、いまのところは Data.Tree とか Data.Graph とかのソースを読んでいます。

GHC って並行 GC あるんでしたっけ？
（並列 GC があるという記述は見つけた。）
というのも System.Mem.Weak.Weak のファイナライザーは別スレッドから（例えば main スレッドしか使っていなかったとして main 以外のスレッドから）呼ばれることを考慮すべきなのかと思いまして。

タイミング的に別スレッドっぽい（ ThreadID 見ろよという話

type instance が定義されてるかのテストってどう書くのがいいんでしょう？

type family Foo :: Type -> Type
type instance Foo Bar = Baz

があったとき Foo Bar はあるけど Foo Qux はないことをテストに書きたい。

自己解決した
追加情報として、別モジュールで type instance Foo Qux = Quux があって、 Quux でないことが確認できればよかったので次のように書けた

do
  let
    target :: Foo Qux ~ Quxx => ()
    target = ()
  shouldNotTypecheck target

でうまくいったっぽい
Foo Qux が本当になかった場合はどう書けるんだろう

それはそれとして、本物の並行GCがGHC 8.10で使えるようになるという噂も　

@ has joined the channel

ちょっとhaskellの話ではなくって数学の初歩みたいな質問失礼します(ここで聞いていいのかな…)
減法のプロパティベーステストを書きたいのですが、減法の性質ってなんなのでしょうか…(どういう条件を満たせばいいのかが調べてもわからなかったです…)
ここで言いたい`条件`というのは、例えば加法で言えば以下のようなものです(これは調べられました)

a + b = b + a
a + 0 = a
(a + b) + c = a + (b + c)

減法の性質というよりは -1 がどのように導入されるかという話になりますが、

- 自然数 N を考える
- n ∈ N なる元を取ったときに、n + m = 0 となる m は (n = 0 のときを除いて) N に存在しない
- ここで、N 上の代数方程式 N[x] に関して、x^2 = 1となる特別な元 -1 を考え、N に添加 (代数拡大) する
- これにより、n + m = 0 をみたす元として m = -n (-1 × n) を考えることができるようになる

という感じが多いと思います。つまり、減法の性質もあくまで加法の性質と同様で、元として -1 も含まれているだけ、ということです

---

テストの書き方は他のHaskell強者の方にゆずります :pray:
(∀n ∈ Z，∃!m ∈ Z，n + m = 0 を書ければ良いと思いますが)

厳密な資料だとこのあたりが参考になると思います↓
https://www.slideshare.net/yoshihiromizoguchi/ss-28541012

ありがとうございます！！
haskellの - の実装を見て n - m = n + negate m と書けるのは確認してましたが、数学的にはそう考えるのですね…
難しいけど楽しい。とても為になりました！
今の数学力でどこまで行けるかわからないですが資料も読んでみます。ありがとうございます

RIO使用時、 Storable のインスタンスを Handle から一個読み込むのに、なにか良い感じの書き方はあるでしょうか。

liftIO $ BS.hGet h (sizeOf @Int32 undefined) >>= BS.useAsCString `flip` (peek @Int32 . castPtr)

でいいでしょうか

allocaなどで環境にバッファを確保しておいて、hGetBufからのpeekをすると効率がよいはずです

hGetBuf見落としてました。ありがとうございます！

余談になりますが、一般的に可換モノイド（今回のケースでは自然数）から可換群（今回のケースでは整数）を構成するグロタンディーク構成というのがあるようです。
自然数から整数への具体的なグロタンディーク構成（本質的に Guvalifさんが紹介されている資料の方法と同じですが）については
https://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0#%E5%8E%B3%E5%AF%86%E3%81%AA%E6%A7%8B%E6%88%90

@Dr_Radialist(KAMAKURA) has joined the channel

こんばんは. Haskell & Parsec入門者です
Parsecを使ってパーサーを作っているのですが、
>=, >, <, <=をパースする関数がどうも不格好で冗長な見た目をしています。
もっとわかりやすく書くために、こういう書き方もあるよ、というのがあれば教えていただけませんでしょうか

-- relational ::= add | add ("<" add | "<=" add | ">" add | ">=" add)
relational :: Parser Expr
relational = do
    a <- spaces *> add
    (do
            spaces *> char '<'
            (Lt a <$> (spaces *> relational))
                <|> (Lte a <$> (char '=' *> spaces *> relational))
        )
        <|> (do
                spaces *> char '>'
                (Gt a <$> (spaces *> relational))
                    <|> (Gte a <$> (char '=' *> spaces *> relational))
            )
        <|> pure a

コード全体はこちらにあります。
https://github.com/mrsekut/hcc/blob/master/src/Parser.hs

今回の質問の主点は上記の部分ですが、もしコードを見てくださった上で気になる点があればご指摘いただけると嬉しいです。
僕のレベル感としてはこんな感じです。↓
State,Maybe,Eitherモナド→なんとなくわかった
STモナド、モナド変換子、Parsecのlexemeとかの使い方や概念を理解していない、パーサーとパーサコンビネータの見分け方を知らない

雑な質問ですがよろしくお願いします

@Kohei Yamamoto has joined the channel

よくあるパーサー作りのこつとして、あらかじめ空白文字をスキップするようにラップしたバージョンを用意する、という方法があります。
例えば「プログラミングHaskell」という本の第1版では（恐らく最近出た第2版でも同じ話があります）、下記のようなパーサーを作ることで、空白文字のスキップを楽にしています。

token p = do
  space
  v <- p
  space
  return v

nat = do
  xs <- many1 digit
  return (read xs)

-- natの「前後の空白をスキップするバージョン」を作っておく
natural = token nat

こんな感じで @mrsekut さんのパーサーについても、 spaces *> ... という部分を抽象化するだけで結構すっきりするのではないかと思います。

ありがとうございます！
アドバイスを受けて修正をしようとしたのですが、うまくいきません。。。
アドバイスの一歩前段階の以下のような変形です

↓元のやつ。factorは “(123)“も”( 123 )“もパース可能

-- factor ::= '(' expr ')' | nat
factor :: Parser Expr
factor =
    (spaces *> char '(' *> spaces *> expr <* spaces <* char ')' <* spaces)
        <|> spaces
        *>  nat
        <*  spaces


-- nat ::= '0' | '1' | '2' | ...
nat :: Parser Expr
nat = Nat . read <$> many1 digit

少し変形したもの。 factorは“(123)“も”( 123 )“もパース不可能

-- factor ::= '(' expr ')' | nat
factor :: Parser Expr
factor =
    (spaces *> char '(' *> spaces *> expr <* spaces <* char ')' <* spaces) <|> h


-- nat ::= '0' | '1' | '2' | ...
nat :: Parser Expr
nat = Nat . read <$> many1 digit


h :: Parser Expr
h = space *> nat <* space

ただfactorの一部をhとして取り出しただけの間隔なのですが、挙動が全く異なるものになってしまいます。
モナドの場合はこういった雑な取り出しはできないのでしょうか

<|> と <*, *> の演算子の結合が、変更前後で意図しない形に変わってしまっているのではないかと。
と、思ったけどすみません、違いますね...

GHCiで調べたところ、

> :i (<|>)
class Applicative f => Alternative (f :: * -> *) where
  ...
  (<|>) :: f a -> f a -> f a
  ...
        -- Defined in ‘GHC.Base’
infixl 3 <|>
> :i (<*)
class Functor f => Applicative (f :: * -> *) where
  ...
  (<*) :: f a -> f b -> f a
        -- Defined in ‘GHC.Base’
infixl 4 <*
> :i (*>)
class Functor f => Applicative (f :: * -> *) where
  ...
  (*>) :: f a -> f b -> f b
  ...
        -- Defined in ‘GHC.Base’
infixl 4 *>

もしかして h に切り出したときに spaces から space に変わってしまっているから？

捕捉: 私が例示した「プログラミングHaskell」に出てくるパーサーはParsecではなくオリジナルなものなので、 space と spaces のように、言葉遣いが違います... :bow:

パーサあまり詳しくないのですが、以下のように構文木を書き換えるのはどうでしょうか。

relOp ::= "<" | "<=" | ">" | ">="
relational ::= add | add relOp add

relOpは以下のように書けると思います(動作未検証)

relOp :: Parser (Expr -> Expr -> Expr)
relOp = l <|> g
  where
    l = do
      char '<'
      (char '=' *> pure Lte) <|> pure Lt
    g = do
      char '>'
      (char '=' *> pure Gte) <|> pure Gt

同じく空白の件ではなくて、元のrelational関数の見通しを良くする件です。
込み入ってきたら、以下のように一旦ベタっと書いてしまう手もあります。 入れ子の中身をwhere節に追い出すのと、比較演算子の文字がかぶるのを try を使って素直に書いてしまいます。好みですが^^ (検証していないので、優先度ミスなどで期待通りに動かないかも。 あと、where節はほぼ同じパターンの繰り返しなので、さらにまとめられます。)

relational :: Parser Expr
relational = do
    a <- add
    try (lte a) <|> (lt a) <|> try (gte a) <|> (gt a) <|> pure a
  where
    lte t = Lte t <$> (string "<=" *> relational)
    lt  t = Lt  t <$> (char   '<'  *> relational)
    gte t = Gte t <$> (string ">=" *> relational)
    gt  t = Gt  t <$> (char   '>'  *> relational)

そこからさらに、 <|> の替わりに choice を使って、まとめてしまうことも。

relational :: Parser Expr
relational = do
    a <- add
    choice $ map try
        [ Lte a <$> (string "<=" *> relational)
        , Lt  a <$> (char   '<'  *> relational)
        , Gte a <$> (string ">=" *> relational)
        , Gt  a <$> (char   '>'  *> relational)
        , pure a
        ]

あと、余談ですが、 chainl1 を使って、全体をコンパクトに書く原典が以下にあります。 （as_capablさんスタイルですね。）
http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf

chainl1 を使うと、例えば以下のようにも書けます。 どこで止めるかは、保守性/可読性含めて好み次第ですね。

-- relational ::= add (relop add | e)
relational :: Parser Expr
relational = add `chainl1` relop

relop :: Parser (Expr -> Expr -> Expr)
relop = choice $ map try 
    [ Lte <$ string "<="
    , Lt  <$ string "<"
    , Gte <$ string ">="
    , Gt  <$ string ">"
    ]

-- add ::= term (addop term | e)
add :: Parser Expr
add = term `chainl1` addop

addop :: Parser (Expr -> Expr -> Expr)
addop = Add <$ char '+'
    <|> Sub <$ char '-'