PartialFunction in Haskell

haskell scala

#scala にあって他の関数型言語には見られない機能として、PartialFuncttionがあるが、良いものだと思う(命名は良くない。CheckableFunctionとか他の名前が良かった気がする)。おかげでcollectみたいなメソッドが定義できるし、他にも応用が利く。

という @kmizu さんの発言があったので Haskell でもやっときます。

{-# LANGUAGE TypeOperators #-}

import Data.Maybe

type Open a = a -> a

fix :: (a -> a) -> a
fix f = f (fix f)

close :: Open a -> a
close = fix

type (a :->: b) = Open (a -> Maybe b)

undef :: a :->: b
undef f a = Nothing

applyMaybe :: a :->: b -> a -> Maybe b
applyMaybe pf = close (pf . undef)

defined :: a :->: b -> a -> Bool
defined pf = isJust . applyMaybe pf

apply :: a :->: b -> a -> b
apply pf = fromJust . applyMaybe pf

collect :: a :->: b -> [a] -> [b]
collect pf [] = []
collect pf (x:xs) = if defined pf x then (apply pf x) : collect pf xs else collect pf xs

zero :: Int :->: String
zero f 0 = Just "0"
zero f n = f n

one :: Int :->: String
one f 1 = Just "1"
one f n = f n

two :: Int :->: String
two f 2 = Just "2"
two f n = f n

こんな感じで…

*Main> collect undef [0..3]
[]
*Main> collect zero [0..3]
["0"]
*Main> collect (one . two) [0..3]
["1","2"]

こんな具合。Just と定義しない部分がダサすぎですね…！まあ Scala と違って文法サポートがないので仕方がない。

COMFRK vol3 でもチラリと書きましたが、Open Recursion は部分関数を実現するためにも使えます。ただ、定義されているかどうかみたいなのは素朴な定義では分からないので、定義されているかどうかの情報を戻り値に持たせるために Maybe に包んでやっています。Haskell なら laziness がうまくはまって defined では Just の中身は評価されないので、こんなにシンプルに実装できてハッピーです。OCaml だとどうかな…

真面目にやるなら、部分関数として扱えるものは a -> Maybe b だけではないので、部分関数のための型クラスを作ってやって、[(a, b)] とか Map a b とかもインスタンスにしとくべきでしょうね。Scala ではそうなっています。

class PartialFunction to where
  applyMaybe :: a `to` b -> a -> Maybe b
  apply pf = fromJust . applyMaybe pf
  defined pf = isJust . applyMaybe pf

そんなわけで 2011 年最後の小ネタでした。もうほんと眠いです。意地で起きてる。