haskell-jp / questions #77

@neguse has joined the channel
@stegeman has joined the channel
@stefan_pavikevik has joined the channel
@unno.hideyuki has joined the channel
来ていきなり質問で申し訳ないのですが…、トップレベルの関数に型注釈を書くのと書かないのとで、まるで実行性能が変わってしまうということは、ありますか?

最近、Haskell で AtCoder の問題に挑戦していて、そのように見える場面に遭遇したのですが、どうにもわからなくて。

たとえば、このコードは、2秒以上かかるケースがあって TLE (時間制限超過):
https://atcoder.jp/contests/abc040/submissions/9522041

なんですが、このコードの65行目ー66行目の二行をコメントアウトすると、速くなってしまいます: https://atcoder.jp/contests/abc040/submissions/9545116

なぜなんでしょうか??

※ Vector むけのソートが欲しくて、山本さんのコード () を利用させていただきました。
型注釈がまちがっていて(例えば、保守的すぎて?)、型推論まかせの場合と、注釈を書いた場合とで違う型になっている、とかかなぁ、など思い悩むものの、自分ではわかりそうな気がせず…。
あまりこの手の経験がないので自信がないのですが、
インライン化できなさそうな関数ですし、 https://blog.miz-ar.info/2016/06/writing-efficient-program-with-haskell/#2.specialization じゃないっすかね。
型注釈がなかったときは MonomorphismRestriction が働いて、 Int か何かに特殊化された quickSortVec が作られたのではないかと。
quickSortVec :: _

のように _ を書くと推論した結果を表示してくれるのですが
Int -> Int -> VM.MVector (PrimState m0) a0 -> m0 ()

と推論したみたいです
別途制約が必要だよというエラーが出ている
競プロでこういうハマり方するのヤダなぁ(競プロじゃなくても
igrep さんのに「なるほど」と思い、SPECIALIZE pragma 書いてみようかとしたのですが、なんと書けばいいのかわからなかったりして…

わたしが書いた型注釈は、ghci 上で :t して聞いたものです。
 quickSortVec :: (PrimMonad m, VM.Unbox a, Ord a) =>
                Int -> Int -> VM.MVector (PrimState m) a -> m ()
速いケースは特殊化の最適化がかかってタプルになったのかな
(タプルでもビルドできた
quickSortList :: [(Int, (Int, Int))] -> [(Int, (Int, Int))]
quickSortList :: (Ord a, VM.Unbox a) => [a] -> [a]
最適化のトリガーが何かは識者の意見を待ちたい……
(`quickSortVec` が再帰してるので抽象的な型の注釈をしたときに特殊化されないのかな
いや、specializeを書くんじゃなくて、GHCが最適化してるときに気づいた具体的な型を書くのが正解かと思います。
GHCiの :t がその結果を出したのは、`quickSortList` も多相化されているからではないかと思います。
quickSortList の型を書いていても quickSortVec に型を書かなければ Int に特殊化できていたのは、おそらく quickSortList がインライン化されたからではないかと思います。(GHCが最適化注に気づいて)インライン化した時点で quickSortListInt に特殊化された、と。

なので、 quickSortList に対する型注釈を消した上で :t してみると、kakkun61が今上げたような結果になり、無事最適化がかかると思います。
quickSortVecは引数を取る関数なのでmonomorphism restrictionは関係ないはずです。
すみません、確かにそうでした。
今回のケースはどうして違いが出るのか私にもよくわかりませんし、GHCのバージョン次第で違う結果になる案件な気もします。
いろいろ書きましたが、結論というか教訓としては「型はなるべく具体的になるように注釈しましょう」ですかね(mod_poppo さんのブログの「特殊化する」と同じことだけど
えー、でも、ライブラリは多相にしたい!
ユーザーとしてできることは、
・具体的な型で型注釈をつける(特にPrimMonadやUnbox制約のついた型変数を具体的にする)(SPECIALIZEプラグマでも良い)
・INLINEプラグマをつける(具体的な型注釈をつけるのと同じような効果が見込める)
あたりでしょうか
C++ 使えばいいんじゃないっすか :upside_down_face:
多相で使えるライブラリにしたいのであれば、IOやST, Intなどのよく使う型に対してSPECIALIZEを書きまくるか、INLINEをつけるか、ですね
競プロに限れば「型注釈を書かない」でいいような気がしました。
多相の注釈が最適化(特殊化)を阻害しうるとわかったので(わかったのかな?)、個人的には、ちょっとすっきりしました。
ありがとうございます!
今回のように再帰関数が絡む場合はこういう泥臭いテクニックがあるらしいです。 :serval:
https://mkotha.hatenadiary.org/entry/20131206/1386330227
型注釈を書かなくても型推論で同じ型が推論されるのなら同じコードが生成されてもいいような気がするんですがね……。GHCだとそうでもないのかな……。
そうなんですよね、コンパイラが推論するのと同じ型注釈を書いたからといって、コンパイラの挙動がかわるのは、自明でも自然でもないように思います。
べつに、書いている側としては「特殊化しないでください」というメッセージではないのだけど…
GHC 8.6でコンパイルしてみたところ、型注釈ありの場合となしの場合でほぼ同様の(特殊化された)コードが生成されるようです。
PrimMonad m =>が付く関数定義は全てインライン化するのが定石です。これを忘れると、その中のすべての(>>=)が辞書渡しになるので、非常に遅くなるのは必至です(会社のコードにもそのような部分を見つけたばかりです…)
わかんない&気持ち悪くて、悩んでいたのですが、ここで尋ねてみてよかったです。みなさん、ありがとうございました!
@baldurpet has joined the channel
この件、型注釈を書かないにしても
default (Int, Double)

くらいは書いておいた方がいいかもしれないことに気づきました。
あまり型を省略して整数がIntegerになってしまうと競プロでは困るでしょうし。
stack install gtk

をしようとしたところ、

stack.yamlに
extra-deps:
    - [email protected]:04dacf055fef4e19dd0276a8c2b5df08332877600b0014beecd2eaa764495ec6,3158
    - [email protected]:9b64a376ebaa4f153bba5866a32291fd4bed48147009cce9158ce6533928eba8,4075
    - [email protected]:132f38155fc677430a47ea750918973161c876fb6f281d342ac2f07eb99229ce,5238
    - [email protected]:5691212b07dc4193ea6f8202a625c9515d750b249aeafc659139e29a5ec61436,3116
    - [email protected]:97698bd054bad38756f3ef0220d7684f72e42660d261e9b118aa73419ce9207d,3136
    - [email protected]:690149ea2efb03c783937b69a5ec6ac854806146fd760e28e800634a6c2243c1,3897

こう書いてくださいとあったのでそうしたのですが、ビルドすると
09/glib-0.13.8.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup ...
glib > Configuring glib-0.13.8.0...
glib > build      
glib > Preprocessing library for glib-0.13.8.0..
glib > setup: Error in C header file.
glib >            
glib > /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/time.h:153: (column 17) [FATAL] 
glib >   >>> Syntax error!
glib >   The symbol `__attribute__' does not fit here.

このようなエラーが出てしまいビルドできません。どなたかお助けいただけませんでしょうか?
こちらに似たエラーとその対応が記載されていました
https://github.com/gtk2hs/gtk2hs/issues/276
(GCC 関連の話なので詳細まで理解せずに書いていますが
- https://scrapbox.io/LugendrePublic/Haskell書いてるときになんとなく気をつけていること
- https://haskell.e-bigmoon.com/stack/test/tasty.html

↑のあたりを見て、自分のコードで hspec を tasty で置き換えてみようかなと思い、 hspec-discover のかわりに tasty-discover を見つけました。しかし tasty-discover のリポジトリ () はアーカイブされています。開発が止まっているなら tasty-discover を使うのはちょっと躊躇してしまいます。

tasty-discover を使っている人 (もしいれば)、便利なので気にせず使っていますか?
おぉ、知らなかった、アーカイブされてるの。
最近はもう手書きするようにしてました(tasty-discover をインストールするのがめんどくさくて)
毎度もにょるんですが、Hspecとtastyはそもそも守備範囲が違うので、単純比較できないかと。
私自身tastyを全然使ったことがないので恐縮ですが、ドキュメントを読む限りあくまでもtastyはいろんな種類のテストを一つのテストスイートで記述するためのものであって、少なくともhspecで小さなテストを書いているだけの状態から置き換えても特にメリットがあるとは思えません。
最新のglibはmacOSでビルドできません。手元の環境では https://github.com/gtk2hs/gtk2hs/issues/291#issuecomment-570829903 で通るようになりました。
kakkun61さんにいただいたページはどうやらLinux環境のものっぽい(使っているdpkgと言うコマンドがLinuxのものっぽかったので、、)のでちょっと試せなそうです。

maoeさんにいただいたページのコマンドを試したところ、
cabal: Encountered missing dependencies:
gi-cairo -any,
gi-gdk -any,
gi-glib -any,
gi-gtk -any,
gi-gtk-hs -any,
gi-pango -any,
gi-pangocairo -any,
haskell-gi-base -any

このようなエラーがおきたため、
cabal install gtk --with-gcc=gcc-9

このコマンドを試してみたのですが、gtkのビルド中にこのようなエラー(長いです)が出てしまいました。
Graphics/UI/Gtk/Embedding/Socket.chs:175:6: error:
    • Couldn't match expected type 'Ptr ()'
                  with actual type 'Maybe DrawWindow'
    • In the second argument of '\ (Socket arg1) arg2
                                   -> withForeignPtr arg1
                                        $ \ argPtr1 -> gtk_socket_add_id argPtr1 arg2', namely
        '(fromNativeWindowId windowId)'
      In the expression:
        (\ (Socket arg1) arg2
           -> withForeignPtr arg1
                $ \ argPtr1 -> gtk_socket_add_id argPtr1 arg2)
          (toSocket self) (fromNativeWindowId windowId)
      In an equation for 'socketAddId':
          socketAddId self windowId
            = (\ (Socket arg1) arg2
                 -> withForeignPtr arg1
                      $ \ argPtr1 -> gtk_socket_add_id argPtr1 arg2)
                (toSocket self) (fromNativeWindowId windowId)
    |
175 |     (fromNativeWindowId windowId)
    |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^

Graphics/UI/Gtk/Embedding/Socket.chs:187:3: error:
    • Couldn't match type 'Ptr ()' with 'Maybe DrawWindow'
      Expected type: IO (Maybe DrawWindow)
        Actual type: IO (Ptr ())
    • In the second argument of '($)', namely
        '(\ (Socket arg1)
            -> withForeignPtr arg1 $ \ argPtr1 -> gtk_socket_get_id argPtr1)
           (toSocket self)'
      In the expression:
        liftM toNativeWindowId
          $ (\ (Socket arg1)
               -> withForeignPtr arg1 $ \ argPtr1 -> gtk_socket_get_id argPtr1)
              (toSocket self)
      In an equation for 'socketGetId':
          socketGetId self
            = liftM toNativeWindowId
                $ (\ (Socket arg1)
                     -> withForeignPtr arg1 $ \ argPtr1 -> gtk_socket_get_id argPtr1)
                    (toSocket self)
    |
187 |   {# call unsafe socket_get_id #}
    |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
cabal: Leaving directory '/var/folders/hd/fpfqf1rs28g30x7rcffkyrnh0000gp/T/cabal-tmp-79499/gtk-0.15.4'
cabal: Error: some packages failed to install:
gtk-0.15.4-8aDu81HrSCJZyllLlxBkN failed during the building phase. The
exception was:
ExitFailure 1

gtkのインストールは他のコマンドを用いるのでしょうか?
その辺は認識してはいるのですが、 tasty 推しの 2記事 (上のリンク) を見たので、試してみようとしたところなのです。

テスト結果の出力の見やすさが一番気になります。 hspec は cabal 経由だと環境変数でオプションを渡さないと色がつかないし……

そうですね、tasty にするとして、tasty-discover なしで手で書いても、そんな大規模でもなければいけますね。
$ brew install gcc
$ cabal build --with-gcc=gcc-9

が意図するところは、macOS のデフォルトである clang を呼ぶ gcc コマンドではなく(でしたよね?)本物の gcc を使うようにするということだと思います。なので gcc コマンドで本物の gcc を呼ぶようにシンボリックリンクを張るなりした後に元々の
$ stack install gtk

を実行するとどうでしょうか?
今手元にラップトップがないのですが、gtk のビルドオプションに have-quartz みたいな名前のフラグを有効にする必要があります
extensibleのレコード型 https://hackage.haskell.org/package/extensible-0.6/docs/Data-Extensible-Field.html#t:RecordOf から、envyパッケージのParser https://hackage.haskell.org/package/envy-2.0.0.0/docs/System-Envy.html#t:Parser を作る関数を書いてみたのですが、型エラーを解決できません...
(ソースコードとエラーメッセージはスレッドに続けて張ります)
ソースコード:
{-# LANGUAGE DataKinds           #-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE KindSignatures      #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeOperators       #-}

module Data.Extensible.Envy
  ( recordFromEnv
  ) where


import           Data.Extensible ((:&), Forall, Instance1)
import qualified Data.Extensible as Ex
import           Data.Kind       (Type)
import           Data.Proxy      (Proxy (Proxy))
import           GHC.TypeLits    (KnownSymbol, Symbol)
import qualified System.Envy     as Env


recordFromEnv
  :: forall (xs :: [Ex.Assoc Symbol Type]) h
   . Forall (Ex.KeyTargetAre KnownSymbol (Instance1 Env.Var h)) xs
  => Env.Parser (Ex.RecordOf h xs)
recordFromEnv =
  Ex.hgenerateFor (Proxy :: Proxy (Ex.KeyTargetAre KnownSymbol (Instance1 Env.Var h))) f
 where
  f membership = Ex.Field <$> Env.env (Ex.stringKeyOf membership)
エラーメッセージ:
src\Data\Extensible\Envy.hs:25:88: error:
    • Couldn't match kind 'Symbol' with '*'
      When matching types
        kv1 :: Ex.Assoc * *
        x :: Ex.Assoc Symbol *
      Expected type: Ex.Membership xs x -> Env.Parser (Ex.Field h x)
        Actual type: Ex.Membership xs x -> Env.Parser (Ex.Field h kv1)
    • In the second argument of 'Ex.hgenerateFor', namely 'f'
      In the expression:
        Ex.hgenerateFor
          (Proxy ::
             Proxy (Ex.KeyTargetAre KnownSymbol (Instance1 Env.Var h)))
          f
      In an equation for 'recordFromEnv':
          recordFromEnv
            = Ex.hgenerateFor
                (Proxy ::
                   Proxy (Ex.KeyTargetAre KnownSymbol (Instance1 Env.Var h)))
                f
            where
                f membership = Ex.Field <$> Env.env (Ex.stringKeyOf membership)
   |
25 |   Ex.hgenerateFor (Proxy :: Proxy (Ex.KeyTargetAre KnownSymbol (Instance1 Env.Var h))) f
   |                                                                                        ^
PolyKinds ?
ホントだ... ありがとう...! :joy:
https://qiita.com/A_kirisaki/items/a72cb21be08c6dd7cf92 とかでも言及がない(別の拡張がimplyしてる?)からまさかと思ってたけど PolyKinds か...!
僕は書いたことあるなぁと思って site: PolyKinds って検索したらこんなの出てきた笑
https://matsubara0507.github.io/test-extensible/memo/00.html
カインドでエラーが出るときは、だいたい `PolyKinds` 拡張が足りない
PolyKinds、安易に有効にしたら余計に多相に推論されて却って面倒なことになった苦い思い出があるのであんまり使いたくないんだよなぁ...
でも今回のエラーは確かにPolyKindsですね... *Symbol が合わないっていってるわけだし...
@motohiro686 has joined the channel
@shiketai.35 has joined the channel