問題を解く上での諸注意
- 以下の問題は全て Haskell で解いてください
- コンパイラは
GHC 8.6.5を用いることとします - ビルドツールは
cabalまたはstackを利用してください - 問題の提出方法は
githubのプライベートリポジトリを作成し、そこに全ての内容を含めてください。(また、@waddlaw をリポジトリのコラボレータとして登録してください) - また、問題を解く際の制限はありません。
Googleなり知人の助けを借りるなり好きにしてください。ただし、不特定多数に対して問題の回答を募ることは不可とします。(例: Twitter で回答を募集する。stackoverflow で回答を募集する等) - 問題に誤りが含まれている場合は、それを指摘した上で正しい回答を提示してください。
-- foldr を使ったバージョン
map1 = undefined
-- foldl を使ったバージョン
map2 = undefined
-- unfoldr を使ったバージョン
map3 = undefined
-- fix を使ったバージョン
map4 = undefineddata Free f a
= Pure a
| Free (f (Free f a)){-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
module Main where
data Nat
= Zero
| Succ Nat
type family Add (n :: Nat) (m :: Nat) :: Nat
type family Sub (n :: Nat) (m :: Nat) :: Nat
type family Mul (n :: Nat) (m :: Nat) :: Nat
zero :: SNat Zero
zero = sing
one :: SNat (Succ Zero)
one = sing
two :: SNat (Succ (Succ Zero))
two = sing
-- |
-- 型レベルで 3 + 2 を行うように型を定義してください
add :: SNat (Add (Succ (Succ (Succ Zero))) (Succ (Succ Zero)))
add = sing
-- |
-- 型レベルで 3 - 2 を行うように型を定義してください
sub :: SNat (Sub (Succ (Succ (Succ Zero))) (Succ (Succ Zero)))
sub = sing
-- |
-- 型レベルで 3 * 2 を行うように型を定義してください
mul :: SNat (Mul (Succ (Succ (Succ Zero))) (Succ (Succ Zero)))
mul = sing
main :: IO ()
main = do
print zero
print one
print two
print add
print sub
print mul
-- singleton
data SNat n where
SZero :: SNat Zero
SSucc :: SNat n -> SNat (Succ n)
deriving instance Show (SNat n)
class Singleton (n :: Nat) where
sing :: SNat n
instance Singleton Zero where
sing = SZero
instance Singleton n => Singleton (Succ n) where
sing = SSucc (sing :: SNat n)論理式を表す Prop 型は以下のように定義されているとします。
data Prop
= Const Bool
| Var Char
| Not Prop
| And Prop Prop
| Imply Prop Prop
deriving Show具体的な論理式の例
p1 :: Prop
p1 = And (Var 'A') (Not (Var 'A'))
p2 :: Prop
p2 = Imply (And (Var 'A') (Var 'B')) (Var 'A')
p3 :: Prop
p3 = Imply (Var 'A') (And (Var 'A') (Var 'B'))
p4 :: Prop
p4 = Imply (And (Var 'A') (Imply (Var 'A') (Var 'B'))) (Var 'B')トートロジーかどうか判定する関数 isTaut に、上記の論理式を適用した結果
> isTaut p1
False
> isTaut p2
True
> isTaut p3
False
> isTaut p4
True- aeson
- extensible
- hspec
- megaparsec
- optparse-applicative
- path
- path-io
- persistent
- quickcheck
- req
- rio
- servant
- yaml
諸注意
- 作成するアプリケーションは何でも大丈夫です
- 上記以外のライブラリを含むこともOKです
- 上記ライブラリの組み合わせ数が多いほど Good
module SpaceLeak where
import Data.List
import Data.List.Split
simulate :: [Int] -- 盤面の状況
-> [Int] -- 次に置く石
-> [Int] -- 各手番における得点
simulate xs [] = []
simulate xs (m:ms)
| m `mod` 23 == 0 = let (as,b:bs) = splitAt (length xs - 7) xs
in m+b : simulate (bs++as) ms
| singleton xs = 0 : simulate (m:xs) ms
| otherwise = let (as,bs) = splitAt 2 xs
in 0 : simulate (m:bs ++ as) ms
singleton :: [a] -> Bool
singleton [_] = True
singleton _ = False
runsim :: Int -> Int -> [(Int, Int)]
runsim p m = sort $ flip zip [1..] $ map sum $ transpose $ chunksOf p $ simulate [0] [1..m]上記のプログラムはスペースリークを含んでいます。
以下の問いに答えてください。
- スペースリークが起きていることを確認する方法について説明してください
- プログラムを修正し、スペースリークを解消してください
- なぜ 2 の方法でスペースリークが修正されるのか説明してください
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE UndecidableInstances #-}
import Data.Aeson
import Data.List (stripPrefix)
import Data.Maybe (fromMaybe)
import Data.Proxy (Proxy (..))
import Data.Text (Text)
import Data.Vector (Vector)
import GHC.Generics (Generic, Rep)
import GHC.TypeLits (Symbol, KnownSymbol, symbolVal)
-- |
-- Strip a prefix from each record field name. Use with via deriving.
newtype StripPrefix (s :: Symbol) a =
StripPrefix a
instance ( Generic a
, GFromJSON Zero (Rep a)
, KnownSymbol s )
=> FromJSON (StripPrefix s a) where
{-# INLINE parseJSON #-}
parseJSON = fmap StripPrefix . genericParseJSON options
where options = defaultOptions { fieldLabelModifier = drop' }
drop' = fromMaybe <*> stripPrefix (symbolVal (Proxy @s))
data Req = Req
{ reqPath :: Vector Text
, reqTimings :: Vector Double
}
deriving stock Generic
deriving FromJSON via StripPrefix "req" Reqrepl による動作確認
λ stack repl --package aeson --package vector --package text
> :set -XOverloadedStrings
> Req "dummy" 0
Req {reqPath = "dummy", reqTimings = 0}
> decode "{\"Path\":\"dummy\",\"Timings\":0}" :: Maybe Req
Just (Req {reqPath = "dummy", reqTimings = 0})なぜ、req という接頭辞が無い json の値をデコードして Req 型の値に変換することができるのか説明できればOKです。