Browsing “24 Days of GHC Extensions” (2014)

2014年のChristmas Advent Calendar — 24 days of GHC Extensionsのメモ

1. View Patterns

パターン変数は左から順に束縛されるので、

{-# LANGUAGE ViewPatterns #-}
find' :: Int -> [Int] -> String
find' x (elem x -> True) = "OK"
find' _ _ = "Nothing"

ということができる。

2. Pattern Synonyms

型間の変換が必要な場合、Pattern synonymを使うとパターンマッチのコストを削減できる。

-— | 型およびその変換関数群を定義する
data ClauseStatus = Normal | Conflict
toNumber :: ClauseStatus -> Int
toNumber Normal = 0
fromNumber :: Int -> ClauseStatus
fromNumber 0 = Normal
—- | 目的関数
activity :: Int -> Int
activity (fromNumber -> Normal) = 0
{-# PatternSynonyms #-}
-- | ClauseStatus型は削除してpatternを定義
pattern Normal = 0 :: Int
activity Normal = 3

変数定義でも同じことはできそうだけど、pattern synonymは大文字で始まっているところに注目。これは型レベル化ということ?
そして ‘without the runtime overhead‘らしい。

ghc-7.8.3 manual によれば、構文は2つある:

  • pattern Name vars <- pat — uni-directional (pattern-only) synonyms(右辺の変数が必ずしも左辺に出現しない)
  • pattern Name vars = pat — simply-bidirectional pattern synonyms (*pat*が式としても構文解析できる場合)

目的は抽象化のようだ。

bidirectional patterns

patternではdata, newtypeで定義した型にシノニムを付けることができるし、そのシノニムからフィールドの値を取り出すこともできる。そういう意味で双方向と思ったのだけど、上記の解釈の方が正しいようだ。

3. Record WildCards

引数として渡されたdataの各フィールドをフィールド名でアクセスできるようにする構文拡張。

{-#LANGUAGE RecordWildCards #-}
data Worker = Worker
{
workerName :: String
, workerPosition :: String
}

instance Show Worker where
show Worker{..} = show workerName ++ “ @ “ ++ show workerPosition

setterとしても使える(例は原文を参照のこと)。

4. Bang Patterns

Bang Patternは引数をweak head normal formにまで評価する。

5. Rebindable Syntax

Prelude中の関数の定義を変更することができる。

{-# LANGUAGE RebindableSyntax #-}
import Predule — RebindableSyntaxの場合は明示的にimportしなければならないようだ
adds = do
80
60
10
where (>>) = (+)
arith = do (+ 1); (* 10); (/ 3); return
where
(>>) = flip (.)
return = id

この addsは150を返し、arith 2は10.0を返す。

6. List Comprehensions

ParallelListComp

並列代入はzipの別形式

{-# LANGUAGE ParallelListComp #-}
fibs = 0 : 1 : [ x + y | x <- fibs | y <- tail fibs]
-> [0,1,1,2, …]

TransformListComp

全体を表すthen節が使える。CommonLispみたいだ。

{-# LANGUAGE TransformListComp #-}
[ x | x <- [1 ..], then drop 10, then take 2]
-> [11,12]

7. Type Operators

このエントリーは型定義をオペレータを使って書きましたというだけ。

data I a = I { unI :: a } deriving (Show) — Indentity Functor
data Var a x = Var { unK :: a } deriving (Show) — Constant Functor
data UserVar = UserName | UserEmail deriving (Show)
data Sum f g a = InL (f a) | InR (g a) deriving (Show) — combine them
email :: [Sum (Var UserVar) + I String]
email = [ InR (I “Dear “), InL (Var UserName)] — , “, thank you for your recent email to Santa & Santa Inc.”]

変数の数が増えると`email`の型は`Sum (Sum … …) …`とならなければならないが、型オペレータを定義すると:

{-# Language TypeOperators #-}

infix 8 +
data (f + g) a = InL (f a) | InR (g a) deriving (Show) — instead of Sum
email :: [((Var UserVar) + I) String] — And also you can write: `Var UserVar + Var XxxVar + I`
email = [ InR (I “Dear “), InL (Var UserName)] — , “, thank you for your recent email to Santa & Santa Inc.”]

と書けるというだけの例だった。

8. Recursive Do

遅延評価される引数をMonad中で実現するということらしい。以下は木に対する検索と置換を1 pathで実現するコード(これはBirdかOkasakiで見たはず)のmonad版fがMonad値を返すので全体がMonad化されてしまうがrecを使うことでlargest、そして置換コード(thunk)が遅延評価される。

{-# LANGUAGE RecursiveDo #-}
import Control.Monad.Fix
impureMin :: (MonadFix m, Ord b) => (a -> m b) -> RoseTree a -> m (RoseTree (a, b))
impureMin f tree = do
rec (t, largest) <- go largest tree — HERE
return t
where
go smallest (RoseTree x []) = do
b <- f x
return (RoseTree (x, smallest) [], b)
go smallest (RoseTree x xs) = do
sub <- mapM (go smallest) xs
b <- f x
let (xs’, bs) = unzip sub
return (RoseTree (x, smallest) xs’, min b (minimum bs))

細かいことは省略とのこと。

rec comes from the RecursiveDo extension, and while the details are beyond the scope of this post (there’s a whole thesis on it!), we can see here that it serves the same purpose as forming recursive bindings, as we did with let.

9. Nullary Type Classes

型パラメータなしの型クラスが定義できる。こういう感じ。

class Logger where
openLog :: Either () String -> IO ()
addLog :: String -> IO ()
closeLog :: IO ()

instance Logger where
f :: Logger => Int -> IO () — この関数はLoggerクラスに結び付けられる。
f x = do
openLog $ Left () — なのでクラスメソッドが使える
addLog $ “x=” ++ show x
y <- g x
addLog $ “y=” ++ show y
print y
g = return . (1 +)

moduleがexportする関数群を一つにまとめる(Loggerだけexport)するという使い方を考えてみた。
なお、class定義とinstance定義は別のファイルに分けることができるので、インターフェースと実装の分離が実現できる。

10. Implicit Parameters

NullaryTypeClassesの話の続き。もし、複数の実装を使い分けたくなった場合、NullaryTypeClassesのアプローチでは対応できない。かと言ってログ関数を引数として引っ張り回すのも大変。こういう時に使えるのがImplicit Parameters

{-# LANGUAGE ImplictiParams #-}
f = queueNewChristmanPresents []
where ?logMessage = putStrLn . (“[LOG]” ++) — 定義する(lispの動的スコープみたい)
queueNewChristmasPresents :: (?logMessage :: String -> IO ()) => [String] -> IO ()
queueNewChristmasPresents presents = mapM_ (?logMessage . (“Queueing present for delivery: “ ++)) presents

?はimplicit parameterのプレフィックス構文(必須)。implicit parameterは制約の位置に置かれる。?logMessageの定義を変えることで複数の振る舞いを実装できる。タプルにしないと複数個は渡せなさそう。

11. Type Families

{-# LANGUAGE TypeFamilies #-}

特に新しい事はなし。

12. Multi-parameter Type Classes

{-# LANGUAGE MultiParamTypeClasses #-}

ここも特に言うことなし。

11から先は続き物。Multi-parameter type classesでの型が一意に決まらない問題の解決は13回にて。

13. Functional Dependencies

{-# LANGUAGE FunctionalDependencies #-}

これも言うことなし。

14. Deriving

functor, Foldable, Traversable, Data, Typableなどの型メソッドを自動生成する。

{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
data List a = Nil | Cons a (List a)
deriving (Eq, Show, Functor, Foldable, Traversable, Typable, Data)
Data is a type class for abstracting over “data shape” allowing you to write generic code for any user-defined ADT without template Haskell.
Typeable defines a way for generating a value representative of a type and relies on some data types that do not expose constructors so you cannot implement it by hand. … It generates 128 bit fingerprint for a given type and nests fingerprints for type parameters if there are any.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}を使うとnewtypeに関しても同様のことができるようだ。

15. DeriveGeneric

The (relatively) new DeriveGeneric extension allows us to use a paradigm of programming called data-type generic programming. In this style of programming, we are able to write our functions over arbitrary data types — provided they have the right “shape”.

2つの型が isomorphic のとき、同じshapeと考えるんだそうだ。これをdata-types generic programmingというらしい。

{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics
data Valid e a = Error e | OK a deriving (Generic, Show)
> :m +GHC.Generics
> :t from
from :: Generic a => a -> Rep a x
> from (OK “aa”)
M1 {unM1 = R1 (M1 {unM1 = M1 {unM1 = K1 {unK1 = “aa”}}})}
> from (Error “e”)
M1 {unM1 = L1 (M1 {unM1 = M1 {unM1 = K1 {unK1 = “e”}}})}
> from (Left “aa” :: Either String String) — Validとよく似たEitherも同じようなものを返す
M1 {unM1 = L1 (M1 {unM1 = M1 {unM1 = K1 {unK1 = “aa”}}})}
class Generic a where
type family Rep a :: * -> * — 表現形?
from :: a -> Rep a x
to :: Rep a x -> a
— Defined in ‘GHC.Generics’

なんだかよくわからない。

16. Overloaded Strings

{-# LANGUAGE OverloadedStrings #-}

ソースコード中の文字列をStringとして型付けするのをやめる。これはソースコード中の数値リテラル1の扱いと同じ(コンテキストによってその型が決まる)。

必要に応じてfromString関数を使うこと。

17. Rank N Types

{-# LANGUAGE RankNTypes #-}

この拡張を用いることでまずforallが使えるようになる。

-— | rank-1 polymorphism
id :: forall a. a -> a
id x = x
-— | rank-2 polymorphism
id2 :: (forall a. a -> a) -> Int
id2 f = f (2 :: Int)
-— | rank-2 polymorphism
id3 :: ((forall a. a -> a) -> Int) -> Int
id3 f = f 2 + f 1
-— and so on

途中で Scott encodingなるものが出てくる(リストを「分解した時にどうするか関数」で定義)。
さらに Church encodingも出てくる(リストを「foldした時にどうなるか関数(継続)」で定義)。その後もなんだか色々出てくる。盛り沢山。

18. Existential Quantification

forallを型定義時に使えるようにする。元エントリーでは何ができると明示してなくてわかりにくいので、[haskell wiki]より引用:

{-# LANGUAGE ExistentialQuantifications #-}
-— | bを隠蔽したい
data Worker x y = forall b . Worker { buffer :: b, input :: x, output :: y }
-— | bを隠蔽したい。さらに制約を付けたい
data Worker x y = forall b . Buffer b => Worker { buffer :: b, input :: x, output :: y }

heterogeneous list、OOPL的な動的ディスパッチなどがこれで実装できる。

19. Scoped Type Variables

{-# LANGUAGE ScopedTypeVariables #-}
-— error version
insertMany :: Ord k => (v -> v -> v) -> [(k,v)] -> Map.Map k v -> Map.Map k v
insertMany accf vs m = foldr f1 m vs
where
f1 :: (k, v) -> Map.Map k v -> Map.Map k v —- 本来はここで`Could not reduce (k ~ k1)`エラー
f1 (k,v) m = Map.insertWith accf k v m

Haskell2010では型変数のスコープが型signatureの行に限定されている。この拡張によりスコープが対応する定義式を含むように拡張される。どこにでも型signatureを書けるようにするのが目的ではなかった。。。

20. Arrows

{-# LANGUAGE Arrows #-}
import Control.Arrow (returnA)
f :: Int -> (Int, Int)
f = proc x -> do
x1 <- (1 +) -< x
returnA -< x1

ArrowはMonadに似たもの。Monad m => Arror mらしいのでdo表記の中で-<という演算子が使える。これは
(-<) :: Monad m => (a -> b) -> a -> m bらしい。pureな関数適用をmonad中で行うもの?

proc-<も構文であって関数(演算子)ではない。

In arrow notation proc plays the part of “lambda”, i.e. backslash, <- plays the part of = and -< feeds an argument into a “function”. We use returnA instead of return.

Arrows拡張(表記)の目的は(Monadでは記述できてしまう)順序依存な計算の記述を不可能にすることにある。具体的には(-<)の左辺は変数のスコープに含まれない:

-— | これはコンパイル&実行可能
f1 y = proc x -> do
x1 <- (+ 1) -< x
x2 <- (if y == 0 then (+ 10) else (+ 100)) -< x1 — yはprocの外の変数
returnA -< x1 + x2
-— | コンパイルエラー
f2 y = proc x -> do
x1 <- (+ 1) -< x
x2 <- (if x == 0 then (+ 10) else (+ 100)) -< x1 — ここでxが未定義エラー
returnA -< x1 + x2
-— | コンパイルエラー
f3 y = proc x -> do
x1 <- (+ 1) -< x
x2 <- (if x1 == 0 then (+ 10) else (+ 100)) -< x1 — ここでx1が未定義エラー
returnA -< x1 + x2

この制約は、最適化、memory leakの防止、意味論を反映したDSL記述などに繋がるだろうとのこと。
なお、Arrowをよく理解するためには圏論(Kleisliカテゴリー)の理解が必要なようだ。

21. Template Haskell

{-# LANGUAGE TemplateHaskell #-}
import Language.Haskell.TH

これはここにまとめるような分量じゃないね。

22. Static Pointers

GHC 7.10 will add a new beast to this list: StaticPtr, the type of pointers whose value never changes across program runs, even across program runs on different machines.
{-# LANGUAGE StaticPointers #-} — 必要?
module Main where
import GHC.StaticPtr — 新しい予約語`static`が導入される
import Data.Dynamic — ???
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n — 1)
-— | non distributed execution
main = do
let sptr :: StaticPtr (Int -> Int)
sptr = static fact
print $ staticPtrInfo sptr
print $ deRefStaticPtr sptr 10

-— distributed computation (Client side)
compute :: IO ()
compute = print $ fact 10
main = send “some-node” $ closure (static fact) `closureAp` closurePure 10
-— Server side
serverLoop :: IO ()
serverLoop = forever $ ???

分散計算のための拡張。ここで全てのノードで同じコードが実行されるものと仮定されている。

最後に

まとめの言葉 closing words

Show your support

Clapping shows how much you appreciated Shuji Narazaki’s story.