haskell-jp / questions #2

再帰/余再帰という言葉は「数学的帰納法」と関連が深くて、帰納/余帰納とも呼ばれます。
数学的帰納法で任意の自然数nについて性質p(n)が成り立つことの証明をすることを思い出してみます。
(i) Base case: p(0) が成り立つことを示す。
(ii) Hypothesis: ある自然数kについてp(k)が成り立つとする。
(iii) Step case: (ii)の仮定の下で、p(k+1)が成り立つことを示す。
(iv) (i),(ii),(iii) より、任意の自然数nについてp(n)が成り立つと主張して証明終わり。
なぜこれで全ての自然数についての証明になっているかというと、全ての自然数は、0(ないしは1)から順に1を足していったものになっているからです(ペアノの公理)
帰納的データ型を扱う関数は、これとそっくりな書き方ができます。
例えば、リストを処理する関数fを書くとします。
f :: [a] -> b
-- Base case: 0の場合に相当
f [] = z
-- Step case: k+1の場合に相当
f (x:xs) = x ⊕ f xs

なぜこれで全ての 有限な リストに対する関数を定義したことになるかといえば、全ての有限なリストは、 [] (nil)に対して : (cons)で一つずつ要素を追加していくことで作られているからです。
有限なリストのように、構造が帰納的(0から順に組み立てていくようなやり方)に定義されているデータ型を「帰納的データ型」と呼びます。
じゃあ無限リストはどうかというと、どこまでいってもbase caseにたどり着きません。そもそも、そういう作られかたをしていないからです。このようなデータに対しては、帰納的に処理を記述することができません。
iterate とか unfoldr が典型的な余再帰のための関数ってことですよね!
Macをお使いの方に聞きたいのですが、 brew install haskell-stack したときって今でもGHCやcabalがOSにインストールされている場合はそのGHCでソースからビルドする、という面倒な仕様なのでしょうか?
formulaを見ると、以下のような記述があるのでおそらくそのままになっていると思います。
system "stack", "-j#{jobs}", "--local-bin-path=#{bin}", "install"
https://github.com/Homebrew/homebrew-core/blob/master/Formula/haskell-stack.rb か。みたいですね。。。これはとても簡単なインストール方法とはいえないな。。。やっぱり報告しようか。。。
そうですね...
あるいは何か問題があってこのような形式になっているかもしれないのですけれども...
newtype Show a => Foo a = Foo a みたいなコードってコンパイル通らないと思うのですが(deprecated な DatatypeContexts を要求される), stack new Foo して上記のコードのみ書き足して stack build すると一言もなくコンパイルが通って挙動も想定通りになります.`stack ghci` はちゃんと通さない.stack か何かのバグ…なんでしょうか?
追記: i) 問題かどうか(僕の勘違いじゃないか) ii) 既知かどうか iii) なんでやねん あたりで疑問に思っています.
DatatypeContexts は分からないのですが、 stack build --pedantic とすると警告が出るかもしれません。
ありがとうございます. --pedantic でも警告はでないようですね.どこで消えてるんだろう…
実際にstackがどのようなオプションをghcに渡しているかを stack build --cabal-verbose で見てみると, -XHaskell2010 が渡されているのが確認できます.つまり stack build 時には stack new で生成したcabalファイルに含まれる設定 default-language: Haskell2010 が有効となり,これは DatatypeContexts を包含しているのでエラーが出なくなります.一方 stack ghci でも同様に stack -v ghci でghcに渡されるオプション(と,一応ghci-scriptとして渡されるファイルの中身)を確認してみると,こちらではdefault-languageが渡されていません.ghciの場合でも stack ghci --ghci-options=-XHaskell2010 としてあげるとbuild時同様にエラーが出なくなることが確認できます.これがstackの想定通りの挙動なのかはわかりませんが,少なくともbuild側についてはcabalファイルに書かれた設定に対し忠実に動作しているように思えます.
関係してググっていて知ったんですが、
https://ghc.haskell.org/trac/ghc/ticket/8026 によると
DatatypeContexts 相当のことを今やりたくなったら GADTs を有効にして
data Foo a where
  Foo :: Eq a => a -> Foo a

と書けばいいんですってね。 :naruhodo:
なるほど!すごくスッキリしました,ありがとうございます. -XHaskell2010 のあたりを全然意識してなかったので教えていただけてよかったです.
実際のところ、DatatypeContextsはGADTsと違い、パターンマッチしてもコンテキストが使えるわけではない非常にむなしい機能なんですよね…
@tanimocchi has joined the channel
ghc-paths-0.1.0.9がGHC-7.0.4と7.2.2でビルド出来ないみたいなんですが、これはパッケージそのものの問題として報告したほうがいいんでしょうか?cabalをよく理解していないがためにパッケージの問題なのか原因を絞り切れないので助けを借りたいです。

Travis CIでのログ(他のGHCバージョンでも失敗していますがそれは無関係です)
https://travis-ci.org/Hexirp/doctest-driver-gen/builds/284639068
要約: ビルド方法が悪いのかパッケージのせいなのか知りたいです。

自分でforkしてビルドした結果
https://travis-ci.org/Hexirp/ghc-paths/builds/288111730
そのビルドには原因とおぼしきエラーメッセージが一切ないので全く分からないのですが、
https://travis-ci.org/Hexirp/ghc-paths/jobs/288111731
こちらのフォークしてビルドした結果にある
Linking /tmp/ghc-paths-0.1.0.9-4199/ghc-paths-0.1.0.9/dist/setup/setup ...
unrecognized option `--disable-benchmarks'

これが原因だとすると、 Setup.hs が想定しているCabalのバージョンと、cabal-installのバージョンが離れすぎているんじゃないか、と思えます。
そもそも、なんでそんな古いGHCでコンパイルしようとしているのでしょうか。。。?
報告してもあまり対応してくれなさそう。。。
cabal ファイルの custom-setup が 1.24 からで、実際に使ってるのが 1.16 だからかな
https://www.haskell.org/cabal/users-guide/developing-packages.html?highlight=custom%20setup#custom-setup-scripts
Warning: ghc-paths.cabal: Ignoring unknown section type: custom-setup
custom-setup についてはあくまで警告ですし、関係ないんじゃないっすかね。
答えていただいてありがとうございます。これだけ昔のGHCに対応しようとするとやっぱり色々問題が出てきますね。諦めることにします。

恥ずかしいことに報告しても対応してくれなさそうという視点は持っていませんでした…
haddockで spliceURL UnhelpfulSpan というエラーがでてコケるんですがworkaround等ご存じの方いますか?

stack-1.5.1で のドキュメントを生成しようとしてこのようなエラーになりました。
https://github.com/haskell/haddock/pull/558 のPRでfixされているような気がしますがstack upgradeしても変わりませんでした(まだ更新されていない?)
スレッドにエラーメッセージを貼っておきます
~$ stack haddock --no-haddock-deps
sdlight-0.9.0.6: build (lib)
Preprocessing library sdlight-0.9.0.6...
sdlight-0.9.0.6: haddock
Running Haddock for sdlight-0.9.0.6...
Preprocessing library sdlight-0.9.0.6...
Warning: The documentation for the following packages are not installed. No
links will be generated to these packages: fail-4.9.0.0


(省略)

Warning: SDLight.Widgets.Internal.Named: could not find link destinations for:
    ~
Warning: SDLight.Widgets.Core: could not find link destinations for:
    WConfigR
Warning: SDLight.Widgets.Effector: could not find link destinations for:
    Op'Appear Op'Disappear Op'GetAlpha Op'IsAppeared Op'IsDisappeared Op'Start Op'GetValue
Warning: SDLight.Widgets.Layer: could not find link destinations for:
    Op'GetCounter
Warning: SDLight.Widgets.Balloon: could not find link destinations for:
    Op'Fly
Warning: SDLight.Widgets.InputJapanese: could not find link destinations for:
    Op'GetText
Warning: SDLight.Widgets.MessageLayer: could not find link destinations for:
    Op'IsWaiting
Warning: SDLight.Widgets.ScriptEngine: could not find link destinations for:
    Op'LoadMiniScript SimpleDSL RefImage
Warning: SDLight.Widgets.Selector: could not find link destinations for:
    Op'RenderSelector Op'SetLabels
Warning: SDLight.Widgets.TabSelector: could not find link destinations for:
    Op'GetTabName Op'RenderTabSelector Op'GetCurrentSelector Op'SetTabs
haddock: internal error: spliceURL UnhelpfulSpan
CallStack (from HasCallStack):
  error, called at utils/haddock/haddock-api/src/Haddock/Backends/Xhtml/Utils.hs:79:9 in main:Haddock.Backends.Xhtml.Utils

--  While building package sdlight-0.9.0.6 using:
      /home/ioijoi/.stack/setup-exe-cache/x86_64-linux/Cabal-simple_mPHDZzAJ_1.24.2.0_ghc-8.0.2 --builddir=.stack-work/dist/x86_64-linux/Cabal-1.24.2.0 haddock --html --html-location=../$pkg-$version/ --haddock-option=--hyperlinked-source
    Process exited with code: ExitFailure 1
template haskellで生成した関数をexportしているのが怪しいかもしれません
headだと直ってるというコメントもありますね https://github.com/haskell/haddock/issues/565
そのページの中ほどにある https://github.com/haskell/haddock/issues/565#issuecomment-281133865 で解決したっぽいです。
stack install haddockで最新のhaddockを入れて、それを ~/.stack/programs/x86_64-linux/ghc-8.0.2/lib/ghc-8.0.2/bin のものに上書きしたらいけました
stackが使っているhaddockの更新方法が分からなくて困っていたので助かりました。ありがとうございます :pray: :pray: :pray:
@ncneller has joined the channel
@shunsuke.masuda has joined the channel
オススメのテンプレートライブラリを教えてください。
たとえば、${DOMAIN}みたいな文字列を""とかに置き換えれる機能を欲しています。
どの程度高機能なものを求めているかにもよりますが、
@arowm さんの https://github.com/arowM/heterocephalus はコンパイル時にテンプレートの間違いを検出してくれるのでいい感じですよ!
パッケージをインストールする際に、ビルドには成功しますが、インストール時に
Failed to load interface for ‘Data.Hashable.Generic’
no unit id matching ‘hashable-1.2.6.1-14fEJP30YhAG9w115PODz0’ was found

というエラーが出るんですが何かご存じの方いますか?
ghc-8.2.1とcabal-2.0.0.2を使用しています。
スレッドに詳細を書いておきます。
インストールしようとしているのはこのパッケージです
https://github.com/myuon/widx/tree/feature/widget-modules

以下により詳細なログを貼ります
/home/ioijoi/.stack/programs/x86_64-linux/ghc-8.2.1/bin/ghc returned
ExitFailure 1 with error message:
Failed to load interface for ‘Data.Hashable.Generic’
no unit id matching ‘hashable-1.2.6.1-14fEJP30YhAG9w115PODz0’ was found
CallStack (from HasCallStack):
  die', called at libraries/Cabal/Cabal/Distribution/Simple/Program/Run.hs:171:7 in Cabal-2.0.0.2:Distribution.Simple.Program.Run
  getProgramInvocationOutput, called at libraries/Cabal/Cabal/Distribution/Simple/GHC.hs:1522:11 in Cabal-2.0.0.2:Distribution.Simple.GHC
  libAbiHash, called at libraries/Cabal/Cabal/Distribution/Simple/Register.hs:260:30 in Cabal-2.0.0.2:Distribution.Simple.Register
  abiHash, called at libraries/Cabal/Cabal/Distribution/Simple/Register.hs:239:21 in Cabal-2.0.0.2:Distribution.Simple.Register
  generateRegistrationInfo, called at libraries/Cabal/Cabal/Distribution/Simple/Register.hs:135:25 in Cabal-2.0.0.2:Distribution.Simple.Register
  generateOne, called at libraries/Cabal/Cabal/Distribution/Simple/Register.hs:121:28 in Cabal-2.0.0.2:Distribution.Simple.Register
  register, called at libraries/Cabal/Cabal/Distribution/Simple.hs:770:10 in Cabal-2.0.0.2:Distribution.Simple
  defaultRegHook, called at libraries/Cabal/Cabal/Distribution/Simple.hs:584:20 in Cabal-2.0.0.2:Distribution.Simple
  regHook, called at libraries/Cabal/Cabal/Distribution/Simple/UserHooks.hs:120:5 in Cabal-2.0.0.2:Distribution.Simple.UserHooks
  cmd_hook, called at libraries/Cabal/Cabal/Distribution/Simple.hs:452:38 in Cabal-2.0.0.2:Distribution.Simple
  cmd_hook, called at libraries/Cabal/Cabal/Distribution/Simple.hs:469:4 in Cabal-2.0.0.2:Distribution.Simple
  hookedActionWithArgs, called at libraries/Cabal/Cabal/Distribution/Simple.hs:451:5 in Cabal-2.0.0.2:Distribution.Simple
  hookedAction, called at libraries/Cabal/Cabal/Distribution/Simple.hs:430:5 in Cabal-2.0.0.2:Distribution.Simple
  registerAction, called at libraries/Cabal/Cabal/Distribution/Simple.hs:184:50 in Cabal-2.0.0.2:Distribution.Simple
  defaultMainHelper, called at libraries/Cabal/Cabal/Distribution/Simple.hs:124:19 in Cabal-2.0.0.2:Distribution.Simple
  defaultMainArgs, called at Main.hs:1210:18 in main:Main
cabal: '/home/ioijoi/.stack/programs/x86_64-linux/ghc-8.2.1/bin/ghc' exited
with an error:
Failed to load interface for ‘Data.Hashable.Generic’
no unit id matching ‘hashable-1.2.6.1-14fEJP30YhAG9w115PODz0’ was found
cabal: Leaving directory '/home/ioijoi/program/widx'
CallStack (from HasCallStack):
  die', called at ./Distribution/Client/Install.hs:995:15 in main:Distribution.Client.Install
cabal: Error: some packages failed to install:
widx-0.1.0.0-ENE00C4n2nTCnkzTC7mfaY failed during the final install step. The
exception was:
ExitFailure 1
ちなみに、このパッケージ自体はhashableには依存していませんがすでにhashable-1.2.6.1がインストールされています
試してみたんですけども、僕の環境では widx を依存関係に追加したプロジェクトで普通に使えました。

$ stack --version
Version 1.6.0, Git revision 0e756d486a5a4d6fe03e0d448bb8e706c5834ca1 (5293 commits) x86_64 hpack-0.18.1

$ cat stack.yaml
resolver: lts-9.10
packages:
- .
extra-deps:
- git: 
  commit: master
- colors-0.3.0.2

$ cat package.yaml
name:                test-widx
version:             0.1.0.0
#synopsis:
#description:
homepage:            
license:             BSD3
author:              Author name here
maintainer:          
copyright:           2017 Author name here
category:            Web
extra-source-files:
- README.md

dependencies:
  - base >= 4.7 && < 5
  - widx

executables:
  test-widx:
    source-dirs:      src
    main:             Main.hs


.stack-work を削除して再度実行してみても同じですか?
ブランチはmasterじゃなくてfeature/widget-modulesなのでは?
extra-deps:
- git: 
  commit: feature/widget-modules
- colors-0.3.0.2

かと。
ブランチはmasterじゃなくてfeature/widget-modulesなのでは?
確かにそうですね!変更しても問題ありませんでした。
わかりにくくてすみません、featureブランチの方です
あと、このパッケージはbackpackを使っているのでghc-8.2, cabal-2以上でないとビルドできません。stackはcabal2系に対応していないので、私はcabal-install-2.0.0.2とghc-8.2をstackで入れてパスなどを通したものを使ってビルドしています。
こういうSExpr型に被せたCallowSExpr型があって、

PatternSynonymsでCons''パターンを(Cons'パターンのように)
書きたいんですが、いまいちPatternSynonymsがわかりません…。

(実際に通るコード)

haskell
{-# LANGUAGE PatternSynonyms #-}

data SExpr = Cons SExpr SExpr | AtomInt Int

newtype CallowSExpr = CallowSExpr { growup :: SExpr }

pattern AtomInt' :: Int -> CallowSExpr
pattern AtomInt' x = CallowSExpr (AtomInt x)

pattern Cons' :: SExpr -> SExpr -> CallowSExpr
pattern Cons' x y = CallowSExpr (Cons x y)

main :: IO ()
main = do
  let x = Cons' (AtomInt 1) (AtomInt 2)
  return ()


(通したい追加コード)

haskell
pattern Cons'' :: CallowSExpr -> CallowSExpr -> CallowSExpr
--pattern Cons'' x y <- (growup {- …? -})

y :: CallowSExpr
y = Cons'' (AtomInt' 1) (AtomInt' 2)


愚直にパターンを組み立てようとすると、帰納的なのでこんなになってしまいそう。

haskell
pattern Cons'' (AtomInt' x) (AtomInt' y) = CallowSExpr (Cons x y)
pattern Cons'' (CallowSExpr (Cons (AtomInt x1) (AtomInt x2))) (AtomInt' y) = CallowSExpr (Cons (Cons (AtomInt x) (AtomInt y)) y)
{-... 以下無限に続くと思う -}


Cons''パターンを部分関数的にせずに、書く方法ってないですか?
そういえば、cabal sandboxを使ってるんですか?
それともnew-buildを使ってるんですか?
それとも普通のcabal buildですか?
「インストール」というのはビルドしてからadd-sourceしてcabal installした場合を指してます?
など、再現手順がイマイチ不明瞭なので教えていただきたく。
もっとも、私からぱっとできるアドバイスは、関連するファイル、 .cabal-sandbox とかを一旦削除してやり直せ、ぐらいしか思い浮かばないので、cabalにバグ報告した方がいいんじゃないかと思っています。
@igrep 再現手順についてはこれでいかがでしょうか(git cloneした直後からのログです)
https://gist.github.com/myuon/e49d89b6504cb645cb1d0a53d39e4b77
@wado 私もTH関係かなと思ったんですが、今のコードからTHを取り除いても(makeLenses関係を手書きしても)エラーメッセージは変わりませんでした
多分なんかのバグを踏んだのだろうという気はするんですが、ghcのバグなのかcabalのバグなのか依存してるパッケージに関連したバグなのかも不明なんですがそんな状態でcabalに報告してもいいんでしょうか?
とりあえずもう少し調査を進めつつminimalな例を頑張って作ってみようとは思っています
うーん、確かに。MLで根回しするところからですかね。。。
とりあえず https://github.com/haskell/cabal#communicating に書いてあったのですが、
https://mail.haskell.org/mailman/listinfo/cabal-devel に投げてしまうのはありじゃないかと思います。
ありがとうございます。
エスケーピングが不要なのと、Text.Printf.printf で事足りることを思い出したので、printfを使いました!