ここでは「関数型」は、関数がファーストクラスであることが最低条件とします。つまり、Func<T, …, T> のインスタンスがある C# は満たしていますし、JavaScript や PHP もそうです。あくまで最低条件で実際にはそれらを活用したライブラリーがないと強くはそう言わないと思います。

さて、これら用語でいうと Haskell は「関数型」ですし、ライブラリーのサポートもあるので強くそうです。では、「手続き型」かというと意外に思うかもしれませんが、手軽に手続きも書けます。Web アプリケーションプログラミングなどではバリバリ手続きを書きます。

なので最初の「Haskell というと手続き型とは全然違う関数型なんでしょう？」に対する答としては「Haskell は手続き型であるし、関数型でもあり、それらは全然違うわけではない。」となります。

データの設計がしやすい

Haskell では「代数的データ型」（algebraic data type）を採用しています。代数的データ型は以降 ADT と表記します。代数的データ型は、直和と直積を持つ系です。（Haxe・Rust・Scala・Kotlin・Swift なども有していると聞いています。）

まず、直積について見ていきます。例えば、よくある例で Person という型があって name と age というフィールドがあるとすると、それは Haskell では次のように記述できます。

data Person =
    Person
        { name :: String
        , age :: Int
        }

C の構造体や C#・Java のクラスと同じですね。

値を作るときは次のようになります。

me = Person { name = "Kazuki Okamoto", age = 28 }

次は直和についてです。先の Parson の例の続きで、実は乗客として人を扱うために Parson を作ったとしましょう。さて、乗客からの要望により新たにペットも乗せられるようになりました。「乗客」型は、値として「人」もしくは「動物」ということになります。これを Haskell で記述すると次のように記述します。

data Passenger =
    Person
        { name :: String
        , age :: Int
        }
    | Animal
        { species :: String
        , name :: String
        }

値を作るときは次のようになります。

me = Person { name = "Kazuki Okamoto", age = 28 }
pet = Animal { species = "dog", name = "Max" }

同等のことを C# や Java などでやろうとすると、インタフェース1つとクラスが2つ必要になります。別の相違点として、直和型の場合は乗客は人もしくは動物のみであることは定義から分かりますが、継承でシミュレートした場合はプログラム全体を検索しないと他の種の乗客があるかどうか分かりません。反対に、継承を使った場合は元のコードに手を加えずに拡張ができるということがいえます。

型の定義部でしか値の種類の追加ができないことは、パターンマッチにおいて網羅性チェックができるという利点があります。

case me of
    Person n a -> {- 何らかの処理 -}
    Animal s n -> {- 何らかの処理 -}
-- 例えば 上記の Animal のパターンがなければ次のような警告が出ます
-- warning: [-Wincomplete-patterns]
--    Pattern match(es) are non-exhaustive
--    In a case alternative: Patterns not matched: Animal

Haskell における手続き

手続きを使ったプログラミングの例として、西暦を入力すると平成何年かを出力するようにしましょう。

import System.IO (hFlush, stdout)

main :: IO ()
main = do
    putStr "Christian Era: "
    hFlush stdout
    christianEra <- readLn :: IO Int
    let heiseiEra = christianEra - 1988
    putStr "Heisei Era: "
    putStrLn (show heiseiEra)

実行すると次のようになります。

λ stack runghc .\heisei.hs
Christian Era: 2017
Heisei Era: 29

C 系との違いとしては、関数呼び出し（関数適用）が括弧なしに関数と引数を並べる点、変数への代入（変数の束縛）が … <- … と let … = … の2種類を使い分ける点があり、それを除けば雰囲気で読めるのではないかと思います。

先の例では main の定義の先頭に do キーワードが使われていますが、Haskell では do キーワードを使えば、その式を手続きで書けるようになります。

詳細は省きますが for_ 関数を使えばループを書けますし、IORef などを使えば再代入（再束縛）可能な変数も作れます。

副作用の明示

Haskell で手続きが難なく書けることは示しましたが、ここで Haskell でいいことがあります。それは副作用の種類が型に明示されるということです。

先の例の main は IO () という型になっています。これは IO を副作用として持つことを意味します。他には、Reader r a というものは、読み取り専用の大域変数（型は r）があることを意味します。ST s a は読み書きのできる大域変数があることを意味します。もちろん大域とはいいつつプログラム全体ではなく副作用は局所化されます。（なんか矛盾してるようですけど局所的に大域的なのです。）などなど、アプリ固有の副作用を示す型を作ることもできます。

IO の手続きの中から IO の手続きは呼べますし副作用のない関数も呼べますが、反対に副作用のない関数の中から IO の手続きは呼べません。呼べてしまうと関数に副作用ができてしまうので当然ですね。ST も ST の手続きの中から ST の手続きと副作用のない関数が呼べます。副作用のない関数の中からは ST の手続きを「実行」することができます。副作用は ST の中にのみ影響するので ST 全体を実行することには副作用がありません。ST の中に局所化される副作用しか ST の中には書けないので入出力などは ST の中に書けません。

これは、プログラムのまちがいが起こりにくいのは当然、他人のプログラムを読むときも大変有用です。C# や Java などのオブジェクト指向では手続きのカプセル化には成功しましたが、副作用の有無についても隠蔽してしまいました。

せめて pure 修飾子などがあるとよいですね。一番近いのは IntelliJ IDEA で Java を書いたときに付けられる @Contract(pure = true) ですかね。

まとめ

以上、なぜ自分が Haskell が好きなのかというと次が主要な理由です。

代数的データ型、特に直和型があることはモデルの設計が簡単になる
Haskell で手続きは書きやすいし、実際よく書く
副作用が明示されることは、コードのまちがいが減るし、読みやすい

2017-08-15

C# でランク N 多相

追記：これだと解決できていない。

C# に Sprache というパーサーコンビネーターがあるのだが、最近そいつを継続渡しスタイル（continuation passing style; CPS）にしてやろうと、Haskell のパーサーコンビネーター attoparsec を参考にいじっていた。

そこでこういう型があった。

newtype Parser i a = Parser {
      runParser :: forall r.
                   State i -> Pos -> More
                -> Failure i (State i)   r
                -> Success i (State i) a r
                -> IResult i r
    }

この型単品では C# への翻訳で困らないのだが、次のような関数があると困ったことになる。

plus :: Parser i a -> Parser i a -> Parser i a

そこで StackOverflow で質問してなるほどなーと思ったのでまとめてみる。

newtype は実質型の別名なので（明示的な相互変換が要るが）、plus 型は次のように理解できるわけだ。

plus :: (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)

ややこしいので今回の話題に本質的でない部分を省くと、次のようになる。（意味のあるものではなくなっているが。）

f :: (forall r. r -> r)
  -> ()

この型は C# でいうところの void F<R>(Func<R, R> f) なのではないかと思うかもしれないが次のような場合に問題がある。

static void Main(string[] args)
{
    F(Id);
}

T Id<T>(T t) { return t; }

void F<T>(Func<T, T> f) { // This is not sound!
    System.Console.WriteLine("{0}", f(1));
    System.Console.WriteLine("{0}", f("one"));
}

F<T>(Func<T, T>) を使うところで推論できないとエラーが出、じゃあと T の型を指定しようとすると int にしても string にしても問題があるわけだ。

f の型は F を適用するところでは一意に決めず多相のままにしておきたいわけだ。こういうのをランク 2 多相という。（上述の F はランク 1 多相。）

で、C# はそんな多相をサポートしてないしなんとか回避策がないものかと考えてパッっと出てこなかったんで StackOverflow に聞いてみたら次のような回答が得られた。

using System;

interface IGenericSameTypeFunction
{
    T Apply<T>(T input);
}

public class SimpleIdentityFunction : IGenericSameTypeFunction
{
    public T Apply<T>(T input) => input;
}

class Test
{    
    static void F(IGenericSameTypeFunction function)
    {
        Console.WriteLine(function.Apply(1));
        Console.WriteLine(function.Apply("one"));
    }

    static void Main()
    {
        F(new SimpleIdentityFunction());
    }
}

なるほどなぁ。部分型多相を使うことでランク N 多相を実現するのだな。

2017-07-08

“meaningless REX prefix used” “use of REX.w is meaningless”

コマンドプロンプトや PowerShell でプログラムを実行したときに次のようなエラーが出て困っていた。

[0x7FFE822C2B00] ANOMALY : meaningless REX prefix used
[0x7FFE85B3DDA0] ANOMALY : use of REX.w is meaningless (default operand size is 64)

REX プレフィックスとは何ぞや。

ロングモードでは、64ビット化するにあたり、16ビット時代から存在した1バイトのinc/dec命令であるinc reg16/dec reg16命令(op 0x40〜0x4f)を廃止してこの位置にプリフィックスを再定義した。結果として、4ビット分のビットフィールドが確保された。 http://www.wdic.org/w/SCI/REX%E3%83%97%E3%83%AA%E3%83%95%E3%82%A3%E3%83%83%E3%82%AF%E3%82%B9

なんか CPU 的に意味のないフラグが立ってるっぽいけど、一体なんでなのやら。

stack が ghc-pkg 辺りの出力をパースをしてるらしく、この出力のせいでエラーになってずっと困ってた。

とりあえずググってみたけど、判然とした原因はいまいちなく、ディスプレードライバーが原因やらウイルス対策ソフトが原因やらという感じだったので、試しに導入していたウイルスセキュリティを無効にして Windows Defender を有効にしてみた。

そうしたらメッセージが出なくなった。原理はよく分かってないけど、一事例として。

2017-05-22

関係と代数的データ型との相互変換についての妄想その3

思い付きその2

class QueryUser ? where
    queryUser :: (?) => Key -> MonadDB User

instance QueryUser ? where
    -- queryUser :: (HasFriends ?) => Key -> MonadDB User
    query = …

instance QueryUser ? where
    -- queryUser :: (HasName ?) => Key -> MonadDB User
    query = …

userFriends :: (HasFriends ?) => User -> [User]
userName :: (HasName ?) => User -> [User]

ふむー？userFriends と userName を使った項は、まぁ (HasFriends ?, HasName ?) になりそうな気はするな。HasFriends ? の ? に入る型と対応する値が要る気がする。

そもそもそれぞれでインスタンス実装できるのか？

ConstraintKinds？

“When matching, GHC takes no account of the context of the instance declaration (context1 etc).” ってあるしムリっぽい。 https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_guide/type-class-extensions.html#instance-overlap

GHC 8.0 だとその記述なくなってるな。 https://downloads.haskell.org/~ghc/8.0.2/docs/html/users_guide/glasgow_exts.html#overlapping-instances

とはいえムリっぽいのは変わりなさそうなんで、次は普通にモナドの方針で行ってみるか。

2017-05-17

関係と代数的データ型との相互変換についての妄想その2

Haskell

思い付きその1

型レベルのリストをクエリー函数に与えてやる。（DataKinds が有効）

data Attr = Id | Name | Friends
data User = User { id :: Int, name :: String, friends :: [User] }
query :: Proxy '[??] -> Key -> MonadDB User
userFriends :: Proxy '[Friends] -> User -> [User]

リストだとダメだなーって気付いた。勝手に型の和が取られるわけじゃないからね。

それはそれとして、分からないところが2点。

1つは上記のコードで query の型の ?? って書いているところをどう書けばよいか。やりたいことは「?? の部分に入るのは 'Attr カインドの任意の型」ということを示したい。

しばらく寝かせて思い付いたけど KindSignatures を有効にして下記でいけるっぽい。

data ProxyAttr (t :: [Attr]) = ProxyAttr

もう1つは、下記のをうまいこと推論してくれないのなんでだ。stack --resolver lts-8.12 exec -- ghci -fprint-explicit-kinds -XDataKinds にて。

後から気付いた ProxyAttr を使うとエラーにならなかった。

ghci> :m + Data.Proxy
ghci> data Attr = Id | Name | Friends
ghci> data User = User { id :: Int, name :: String, friends :: [User] } deriving (Show)
ghci> :{
ghci| userFriends :: Proxy '[Friends] -> User -> [User]
ghci| userFriends _ _ = [User 1 "Ada" []]
ghci| :}
ghci> bob = User 2 "Bob" []
ghci> let p = Proxy in userFriends p bob

<interactive>:9:30: error:
    • Couldn't match type ‘*’ with ‘[Attr]’
      Expected type: Proxy [Attr] ((':) Attr 'Friends ('[] Attr))
        Actual type: Proxy * ((':) Attr 'Friends ('[] Attr))
    • In the first argument of ‘userFriends’, namely ‘p’
      In the expression: userFriends p bob
      In the expression: let p = Proxy in userFriends p bob

Proxy に型注釈してやると大丈夫。

ghci> let p = Proxy :: Proxy '[Friends] in userFriends p bob
[User {id = 1, name = "Ada", friends = []}]

どっちにしろリストの戦略は破綻してるのでボツ。

制約の方に情報を乗せないとあかん気がしている。

2017-05-16

関係と代数的データ型との相互変換についての妄想その1

Haskell

OR マッパーみたいな、関係*1とデータ型との相互変換が機械的にできたら嬉しいなという話。

シンプルなのは簡単だしすでにできる。例えば次のような関係がある場合*2、

var user base relation {
  id integer,
  name string,
}
key { id };

var friends base relation {
  user1 integer,
  user2 integer
};

これを単に次のようなデータ型に変換するのはいくらかのライブラリーで実現できる。

data User = User { id: Int, name: String }

data Friends = Friends { user1: Int, user2: Int }

しかし、実際のところ欲しい型というのは次の通りでこれは機械的にできるのはなさそう。（ちゃんとは調べてないのであったら教えてほしい。）

data User = User { id: Int, name: String, friends: [User] }

よくあるクラスベースのオブジェクト指向言語なら Friends ゲッターの中でクエリー発行すればいいんだけど、同じことを Haskell ですると IO まみれになるしできれば純粋な函数にしたいよなー。

public class User {
  public readonly int id;
  public readonly string name;
  readonly IList<User> friends;
  public IList<User> Friends {
    get {
      if (friends == null) friends = …;
      return friends;
    }
  }
  public User query(int id) { … }
}

妄想としては、そのフィールドが使われてるかの情報を型に乗っけることで、DB からの取得時にどれを取ってくればいいか分からないかなーと。

do
  user <- queryUser 1 -- 何らかの queryUser :: Int -> MonadDB User みたいな函数があるとして
  return $ friends user

friends 函数の型を GetFriends user => user -> [User] みたいにしてやることで型推論によって queryUser 函数の型クラス制約にも GetFriends が付いて実装を変えられないかなぁと。

うーんでも型クラスのありなしでは実装は変えられないかー。なんとか型に情報乗せないとダメかな。

続きはまた後日。

*1:ここでいう関係は関係代数の用語としての関係です。

*2:Tutorial D の記法に従ってますが、パーサーにかけたことがないのでまちがってるかもしれない。

関数型プログラミングだから Haskell が好きというわけではない

データの設計がしやすい

Haskell における手続き

副作用の明示

まとめ

思い付き その2

思い付き その1

思い付きその2

思い付きその1