haskell-jp / questions #52

shinji.hatayama709
@shinji.hatayama709 has joined the channel
@fuuzetsu has joined the channel
@oswald_boc has joined the channel
@viktor.kronvall has joined the channel
@onwarmermusic has joined the channel
逆アセンブリした結果は以下のようになりました(一部分だけ)
00000000004fb010 <Main_boolzuvar1_closure>:
  4fb010: b8 c2 4b 00 00        mov    $0x4bc2,%eax
  4fb015: 00 00                 add    %al,(%rax)
  ...

00000000004fb018 <Main_zdtrModule3_closure>:
  4fb018: f8                    clc
  4fb019: c2 4b 00              retq   $0x4b
  4fb01c: 00 00                 add    %al,(%rax)
  4fb01e: 00 00                 add    %al,(%rax)
  4fb020: 00 90 50 00 00 00     add    %dl,0x50(%rax)
  ...

00000000004fb028 <Main_zdtrModule1_closure>:
  4fb028: f8                    clc
  4fb029: c2 4b 00              retq   $0x4b
  4fb02c: 00 00                 add    %al,(%rax)
  4fb02e: 00 00                 add    %al,(%rax)
んー、Cmm と asm の時点では +9 があるんですが、バイナリから +9 が消えているみたい?
@ramin.honary has joined the channel
違いますね。アセンブリ言語に関する知識がなくて頭の中がクエスチョンマークだらけです
あー、とても単純なところを勘違いしていました…… バイナリの中で True_closure+9 である 4fb019 の所を指していることと、実行結果も 0000000000004bc2 である 19394 が表示されることを確認しました。回答していただいたみなさん、ありがとうございました!
このような string literal をコンパイルできる環境を探してます.どういう条件でコンパイルすると通るんでしょう?
https://gitlab.haskell.org/ghc/ghc/blob/master/compiler/main/GHC.hs#L1063
( 今後 master は変更されるかもなので, GHC 8.6.4 版のリンクも貼っておきます: https://gitlab.haskell.org/ghc/ghc/blob/ghc-8.6.4-release/compiler/main/GHC.hs#L1055 )
Haskell2010 上だと, \ の後に空白(改行を含む)を続けて再度 \ があるとそこの部分が無視されるのは知ってるんですが,終わりの \ も無いようですし
ついでに,素の GHC 8.6.3 の GHCi 上で

>>> :{
s = "a\
   \b"
:}
>>> s
"ab"
>>> :{
s = "a\
   b"
:}

<interactive>:8:3: error:
    lexical error in string/character literal at character 'b'


となるのは試しました
これCPPの効果だって某所で聞いた記憶が
なるほど,今それありそうだなって思ってやってみてます
(例のghc-compiler-notesプロジェクトやってたときに、わどさんが同じ箇所で引っかかってCPPによるものみたいです、って教えてもらった)
(今まさに ghc-compiler-notes の書き直しをやってて引っかかってます)
なるほど,こんな話があるんですね( CPP 使ってる場合 string gap が使えないので, CPP のこの機能を使わざるを得ない)
https://downloads.haskell.org/~ghc/8.6.4/docs/html/users_guide/phases.html?#cpp-and-string-gaps
@okimoto has joined the channel
@jesper has joined the channel
@nobsun もしかしてcata . ana合成したhyloだと中間データ構造を作ってしまい,hyloの再帰型だとDeforestationされると理解して良い?…んだよね?
はい.そうです.
さらに hyloを展開してしまって, 直截再帰的に定義してしまえば,psiで生成するMaybe (b,a) も生成しなくていいよね.
buildMap :: (Ord key) => ([Maybe key], [Maybe val]) -> Maybe (Map key val)
buildMap = \ case
  (Just k : ks, Just v : vs) -> Map.insert k v <$> buildMap (ks, vs)
  (Nothing : _, _)           -> Nothing
  (_, Nothing : _)           -> Nothing
  ([], [])                   -> Just (Map.empty)
  (_:ks, [])                 -> const (Map.empty) <$> buildMap (ks, [])
  ([email protected][], _:vs)               -> asTypeOf (Map.empty) <$> buildMap ([], vs)
おお、ありがとうございます
``mkMap :: Ord k => ([Maybe k], [Maybe v]) -> Maybe (Map k v)``を定義しようとして,
```
mkMap :: Ord k => ([Maybe k], [Maybe v]) -> Maybe (Map k v)
mkMap ([], v:vs) = const Map.empty <$> mkMap ([], vs)
```
とすると,この部分で以下のようなエラーがでるのですが,なぜ推論できないんでしょうか?
(ghc-8.6.4)

```
/home/nobsun/work/ny-sketch-book/src/BuildMap.hs:57:40: error:
• Could not deduce (Ord k0) arising from a use of ‘mkMap’
from the context: Ord k
bound by the type signature for:
mkMap :: forall k v.
Ord k =>
([Maybe k], [Maybe v]) -> Maybe (Map k v)
at /home/nobsun/work/ny-sketch-book/src/BuildMap.hs:56:1-59
The type variable ‘k0’ is ambiguous
These potential instances exist:
instance (Ord a, Ord b) => Ord (Either a b)
-- Defined in ‘Data.Either’
instance forall k (s :: k). Ord (Proxy s)
-- Defined in ‘Data.Proxy’
instance forall k (a :: k) (b :: k). Ord (a :~: b)
-- Defined in ‘Data.Type.Equality’
...plus 28 others
...plus 12 instances involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the second argument of ‘(<$>)’, namely ‘mkMap ([], vs)’
In the expression: const Map.empty <$> mkMap ([], vs)
In an equation for ‘mkMap’:
mkMap ([], v : vs) = const Map.empty <$> mkMap ([], vs)
|
57 | mkMap ([], v:vs) = const Map.empty <$> mkMap ([], vs)
| ^^^^^^^^^^^^^^
Failed, no modules loaded.
```
ぱっと思いつくのは、 const Map.empty .... と、戻り値を必ず Map.empty にしてしまっているからではないかと。
asTypeOf に変えたら通りましたし。
これ、ひょっとして本当にやりたいことは const ではなく Map.union ではないでしょうか?再帰の基底部で必ず Map.empty を返してしまったら意味がないような...
やりたいことは,
https://haskell-jp.slack.com/archives/C5666B6BB/p1552378070228900?thread_ts=1551956556.140300&cid=C5666B6BB
です.Map.unionをつかっても同じ意図を実装できますが,なぜ,上の書き方でだめなのかが理解できていません.
mkMap ([], vs) :: Maybe (Map k v)kmkMap :: Ord k => …k が同じだということが分からないような
Map.unionを使うと判るのは...なぜだろう...:thinking_face:
consta -> b -> a という型なので mkMap ([], vs) :: Maybe (Map k v)kMap.empty の型と同じとは限りませんが、
Map.union (や、 asTypeOf )は戻り値も引数もすべて同じ型なのでわかる、ということではないでしょうか?
:sweat_smile:ああそうかなるほど!ありがとうございます.
あらっ? mkMap ([], vs) :: Maybe (Map k v) みたいな型注釈をつけてもいけそうなんだけど...だめなのか...:open_mouth:
ScopedTypeVariables の出番ですかね。 :smirk:
それを指定したんだけど...だめみたい.
forall を書き忘れるというミスを犯してませんか... (経験者談 :sweat_smile:
:sweat_smile: おもいっきりヤラカしてました.ありがとうございます.
@vqgofndplhjr has joined the channel
なにがカッコイイかはよく判らないけれど,プログラムの判りやすさと,時間性能は hylo 版も直接再帰版もオリジナルに敵わないです.
@nobsun 時間性能については、オリジナル版はallとfromListでリストを二回なめているため、hylo版の方が速いかと
ScopedTypeVariables は型変数のスコープの開始を forall で指定するという仕様なのです。
@chinsan514 has joined the channel
オーダーとしては線形で同じなので,あとは実測値でどうかということになると思います.10^6くらいサイズならオリジナルの方が速いみたいですよ.
あー、もしかしてfromListならソートして一気にマップ作れるのに対して、全部insertでやってるから遅いんじゃないですかね
末尾再帰になっていないのがよくない気がします。
リストのソートもMapへのinsertもオーダーとしてはO(n log n)だから,基本オペレーションの性能かでしょうかね.
fromListもfoldで実装されてますね
fromList :: Ord k => [(k,a)] -> Map k a 
fromList xs       
  = foldlStrict ins empty xs
  where
    ins t (k,x) = insert k x t
insertなのか、ちょっと意外です。赤黒木とかならソートしてやった方が速かった木がするんですが、フィンガーツリーだと違うのか
木がするとは