haskell-jp / beginners #8

@akthrms has joined the channel

@kanshuyokoo has joined the channel

@natsuo has joined the channel

@ny has joined the channel

@Setonai has joined the channel

@ has joined the channel

@aiya000 has joined the channel

@HiB has joined the channel

Reminder:
beginnersチャンネルは、新しい人がスムーズにHaskellに慣れるための質問を歓迎するチャンネルです。
Haskell-Beginners ML や IRCの#haskell-beginners や RedditのMonthly Hask Anythingのような位置づけを意図しています。

beginnersチャンネルでの回答側は、以下の左側のような応答を厳禁とする運用です。
• それはくだらない質問だ → くだらない質問など無い
• その質問は以前にもあった → 質問者はそんなこと知らない
• Google検索せよ → 検索できないから質問している
beginnersチャンネルでは、例えば以下のレベルの質問から歓迎します。
• : とは何のことですか。
• タプルとは何ですか。

@ has joined the channel

初めまして！mshojiと申します。
Haskellを学んで日が浅いのですが、Haskellの美しさに魅力を感じて少しずつ勉強をしています。

漠然とした質問で申し訳ないのですが、上級者の皆さんはどのような学習をして、今のレベルまで到達したのでしょうか？
興味があるので、お聞きしてみたいです。

入門書で基本的な文法を学習し終えても、SpockやYesodといったフレームワークを使ったアプリケーションを作成するには、
TypeFamiliesやDataKinsなど様々なGHC拡張を知らないと、バグが出てきた時エラーの解消が難しいのではないか、というのが思うところです。

参考までに、「すごいH本」や「Haskell入門 関数型プログラミング言語の基礎と実践」などは読みました。（完璧に理解しているとは言えないですが。。）
今は、自分の知らない概念や上記のGHC拡張などを、少しずつ消化する形で勉強しています。
次のステップとして、オススメの学習方法とかありますか？（とは言え、こういう概念を少しずつ勉強するのもHaskellの楽しさだと思ったりしています）

※質問自体がふわっとしているので、皆さんの体験談とか聞けるだけでも非常に参考になります。

体験談の一つとして :raising_hand:
僕はいつもRedditでupvoteがある程度ついてる投稿を見て気になるものがあったら深堀りしてます :eyes:
https://www.reddit.com/r/haskell/
で、Redditは話題が多岐に渡るので面白かった記事とか読めてない記事も含めて分類しながらGitHubにまとめている感じです
http://lotz84.github.io/haskell/
他の人の体験談も :kininaru: :wakuwaku:

いろいろやりましたが、GHC User Guideを通読したのは割と大きかったと思います。全部理解しなくてもいいので。
あと体験談じゃないっすけどその他の各論は https://wiki.haskell.jp/Links によい情報をぎゅっとまとめたつもりです。
「ライブラリなどの解説」あたりが特におすすめです。

はじめまして！
私は入門書に乗っていないものが出てきて困ったときに、このサイトも役立ちました。
WHAT I WISH I KNEW WHEN LEARNING HASKELL http://dev.stephendiehl.com/hask/

（因みに、入門書終えたらすぐフレームワークとか使いました。おっしゃるとおりで、知らない機能や複雑なエラーが出たら都度頑張る事にはなりましたが、なんとかなりました

@lotz
ありがとうございます！
Redditはあまり読んだことがないので、とても参考になります！見てみます:smile:

@igrep
GHC User Guide、通読とはレベルが高いですね！数年単位かかりそうです。。でも、これを通読したらかなりレベルアップしそうです:smile:
リンクもありがとうございます！とても参考になりそうです！

@nakaji-dayo
リンク見てみましたが、内容がとても充実していますね！:smile:
勉強する際にとても参考になりそうです！ありがとうございます！

@ has joined the channel

@ has joined the channel

@skaribe has joined the channel

@ysys13 has joined the channel

@minus1216 has joined the channel

@ぽんちゃん has joined the channel

@ has joined the channel

@kuu has joined the channel

@Roki has joined the channel

Reminder:
beginnersチャンネルは、新しい人がスムーズにHaskellに慣れるための質問を歓迎するチャンネルです。
Haskell-Beginners ML や IRCの#haskell-beginners や RedditのMonthly Hask Anythingのような位置づけを意図しています。

beginnersチャンネルでの回答側は、以下の左側のような応答を厳禁とする運用です。
• それはくだらない質問だ → くだらない質問など無い
• その質問は以前にもあった → 質問者はそんなこと知らない
• Google検索せよ → 検索できないから質問している
beginnersチャンネルでは、例えば以下のレベルの質問から歓迎します。
• : とは何のことですか。
• タプルとは何ですか。

@Shota has joined the channel

@kazuki has joined the channel

@Jahon has joined the channel

@Aquila Minakami has joined the channel

@ has joined the channel

Data.Vector.Unboxedについて質問です。

最近競技プログラミングのAtCoderを始めたのですが、Data.Listの計算速度が遅いということで
時折Data.Vector.UnboxedやData.Vector.Unboxed.Mutableを利用しています。

今回は AtCoder Beginner Contest 173 E - Multiplication 4
https://atcoder.jp/contests/abc173/tasks/abc173_e
を解くことを試みました。

Listを使って書いたものが以下です。
https://atcoder.jp/contests/abc173/submissions/15057521
問題には制限時間があり、一定時間内に計算を終えなくてはいけません。
黄色いTLEのマークが時間オーバーを示していて、Data.Listでは上手くいかないのでData.Vector.Unboxedの利用を検討しました。

Data.ListをData.Vector.Unboxedに置き換えるために、
gksatoさんの回答
https://atcoder.jp/contests/abc173/submissions/15013762
を参考にしました。

回答では大きな数をmodで小さくするように要求されており
gksatoさんの回答では、型を作って対応しているようなのですが、
私には少し難しいので、出てきた数字に対して直接modを適用したいと考えています。

起きている問題としては

import qualified Data.ByteString.Char8 as BS
import Data.Maybe
import qualified Data.Vector.Unboxed as VU

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getIntList = readIntList <$> BS.getLine

prod :: VU.Vector Int -> Integer
prod = mod1G7 . VU.product . VU.map fromIntegral

mod1G7 :: Integral a => a -> a
mod1G7 n = n `mod` (10 ^ 9 + 7)

main :: IO ()
main = do
  [n, k] <- getIntList
  as <- getIntList
  let as' = VU.fromList as
  print $ prod as'

入力例

4 2
1 2 -3 -4

としたときに、

abc/173/E.hs:31:17: error:
    • No instance for (VU.Unbox Integer)
        arising from a use of 'VU.product'
    • In the first argument of '(.)', namely 'VU.product'
      In the second argument of '(.)', namely
        'VU.product . VU.map fromIntegral'
      In the expression: mod1G7 . VU.product . VU.map fromIntegral
   |
31 | prod = mod1G7 . VU.product . VU.map fromIntegral
   |                 ^^^^^^^^^^

というエラーが出てしまい、走らないことです。

prod :: VU.Vector Int -> Int

とすると、動作はするのですが、大きい数が来た場合に答えが一致しません。

関数の型のアノテーションを消すと

    • Ambiguous type variable 'a0' arising from a use of 'VU.product'
      prevents the constraint '(VU.Unbox a0)' from being solved.
      Relevant bindings include
        prod :: VU.Vector Int -> a0 (bound at abc/173/E.hs:31:1)
      Probable fix: use a type annotation to specify what 'a0' should be.
      These potential instances exist:
        instance VU.Unbox a => VU.Unbox (Down a)
          -- Defined in 'Data.Vector.Unboxed.Base'
        instance VU.Unbox () -- Defined in 'Data.Vector.Unboxed.Base'
        instance (VU.Unbox a, VU.Unbox b) => VU.Unbox (a, b)
          -- Defined in 'Data.Vector.Unboxed.Base'
        ...plus 10 others
        ...plus 24 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the first argument of '(.)', namely 'VU.product'
      In the second argument of '(.)', namely
        'VU.product . VU.map fromIntegral'
      In the expression: mod1G7 . VU.product . VU.map fromIntegral
   |
31 | prod = mod1G7 . VU.product . VU.map fromIntegral
   |                 ^^^^^^^^^^

のようなエラーが出てアノテーションを利用することを薦められます。

VU.productでVU.Vector Int型の引数からInteger型の返り値を得るためにはどうすればよいでしょうか。
よろしくお願いします。

ちなみに、VU.toListで一度Listにしてproductを適用したものは動いたのですが、同じく時間切れでした。
https://atcoder.jp/contests/abc173/submissions/15058952

unboxed vectorほど動作は速くないですが、unboxedじゃない普通のVector https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector.html はいかがでしょうか？
こちらなら Integer も格納できます。

この問題では、Vector の要素は Int で十分ですが、product をすべてとったあとに mod しようとすると Int ではあふれてしまうのと、Integer をつかったとしてもすごい桁数になって時間内におさまらない可能性が高いです。

なので、掛け算のたびに mod をとってやればよく、** さんのコードでいうと、prod を次のように書いてやればいいように思います。
`prod = VU.foldl1' (\x y -> x * y `mod` (10^9+7))`

これで、とりあえず TLE はしなくなったのですが、 WA がでちゃってますね…


わたし、まだ ABC173E 解いてないんすよ…。

Modular Arithmetic の乗算(かけ算ごとにmodをとる)を定義してしまえば、それでIntの範囲に収まります。しかし、Vectorを使う必要がありますか？ ランダムアクセスしないのなら、[Int]でもよいのではという気がすこしします。確認してませんが(をぃ^^;)、アルゴリズムを少しみなおせば、[Int]でもLTEが出なくなったりしませんか？

ソートする必要があるので、[Int] のままではきつそう…

（AtCoder の C 以降でリストでいけちゃうケースは、あんまり無いような印象があります）

Vectorのソートの方がずっと速いということですか。なるほど。どのくらい違うんだろう。計測してみよう

私

答えていただいたみなさま、ありがとうございました。
結論から言えば、Vectorを使わずに行くことができました。計算時間の問題はunnohideyukiさんのおっしゃるとおり、かけ算毎にmodを取ることで解消できました。
もちろん、modを取ると崩れる関係もあるので、そこも修正する必要がありました。また、nobsunさんのおっしゃる通り、[Int]のままでも時間内に収めることができました。

Vector周りが原因だと思っていたのですが、そんなことはなかったようです。igrepさんもVectorの型について教えてくださりありがとうございました。

https://atcoder.jp/contests/abc173/submissions/15062863

modを取ると崩れる関係もあるので

10^18は64bit Intの範囲なので、絶対値が10^9以下の2つの数の積なら、modを取らずともIntの範囲におさまります。modをとる積を使うのは、最後の最大値を求めるところだけですみそうですね。

え？ 最後の最大値を求めるまでに、3つ以上の数の積は普通に取られますよ？

最後の最大値を構成する組合せを見つけるのには、3つ以上の数の積を計算する必要がないような気がしたのですが。。。

むしろ、そのコード、modをとる積しか使ってないように見えるのですが・・・。

最後の最大値を求めるところだけ。

modを取ると崩れてこまる関係(比較演算子)はないというつもりでした。

35行目

コード中で最後の最大値を求めるところだけ？

いや、違うのはわかるのですが、…

最大値を構成するAiの組合せを求めるのには(><)は使ってないという意味です。紛らわし表現ですみません。