Scala's Partial Functions in Haskell

Question

Scala has a very nice support of partial functions, mainly because in Scala when you define a partial function it also defines an isDefinedAt function for it. And also Scala has orElse and andThen functions to work with partial functions.

Haskell does support partial functions by simply non-exhaustively defining a function (though they are strongly discouraged in Haskell community). But to define isDefinedAt function in general you have to use some sort of exception handling, which I'm not being able to figure out. Once isDefinedAt function is defined then it can be used to define orElse and andThen function is already there as (.).

In short, I want to define a function,

isDefinedAt :: (a -> b) -> a -> Bool
isDefinedAt f x = -- returns True if f is defined at x else False

Can anyone please tell me how such a function can be written.

Note, I can define a function with signature

isDefinedAt :: (a -> b) -> a -> IO Bool

for generic b. But I want a function without IO in co-domain.

A nice article on Scala's Partial Functions is - How to create and use partial functions in Scala By Alvin Alexander

Reluctance

By 'defined' do you mean 'not undefined'? Why not just use Maybe? – Merla

It is, by design, not possible to catch exceptions in Haskell without using IO. As you say, partial functions are strongly discouraged; if you write a partial function you should consider your responsibility to make sure it will never actually be called outside of its domain. If that can't be guaranteed up front, you should make it explicit that the function can fail through a suitable result type. – Loveland

@Loveland I know and completely understand what you are saying, but still this negative attitude towards partial functions seem a bit dogmatic to me. There are good reasons to use partial functions, for example head and tail functions. And using Maybe in co-domain in many such cases doesn't seems honest, as when someone thinks of head function, s/he thinks of it as a function NOT defined on empty list, so I do want my program to crash if I ask her to compute 'head []' with the error saying it's not defined, preferably. – Reluctance

Answer 1

I recommend that, like in Scala, you use a separate type for partial functions.

import Control.Arrow
import Data.Maybe

type Partial = Kleisli Maybe

isDefinedAt :: Partial a b -> a -> Bool
isDefinedAt f x = isJust $ runKleisli f x
-- laziness should save some of the work, if possible

orElse :: Partial a b -> Partial a b -> Partial a b
orElse = (<+>)

andThen :: Partial a b -> Partial b c -> Partial a c
andThen = (>>>)

Hairline

Thanks Daniel for the suggestion. I'm accepting your answer as it's good enough for me, but I was thinking if there is a way to converting the non-exhaustively defined function (which, let's say, I already have in code and don't want to change) to a Partial. I can't seem to find one. And if there is no way then what's the reason for it. – Reluctance

Answer 2

Your versions of isDefinedAt are not what Scala does (even in signature); it's very possible (though discouraged) for a PartialFunction to throw an exception when isDefinedAt is true. Or, when you define one explicitly (not using a literal), vice versa: apply doesn't have to throw when isDefinedAt is false, it's user responsibility not to call it then. So the direct equivalent would just be

data PartialFunction a b = PartialFunction { apply :: a -> b, isDefinedAt :: a -> Boolean }

which isn't particularly useful.

apply and isDefinedAt are only really linked in Scala for PartialFunction literals which requires compiler support:

A PartialFunction's value receives an additional isDefinedAt member, which is derived from the pattern match in the function literal, with each case's body being replaced by true, and an added default (if none was given) that evaluates to false.

You can emulate this by using Template Haskell, I believe, but I honestly think using the more Haskell-like approach as described in Daniel Wagner's answer is better. As he mentions, laziness helps.

Though it works even better if you make sure runKleisli f x is executed only once; optimizing cases where you have both isDefinedAt and runKleisli requires Common Subexpression Elimination, and the compiler is cautious about doing that, see Under what circumstances could Common Subexpression Elimination affect the laziness of a Haskell program?

Kulp

I think the OP is more interested in the properties of the PartialFunction type rather than the PartialFunction literal. – Ibarra

And it's an important property of PartialFunction type that isDefinedAt result value has no connection to whether apply will throw exception. – Kulp

Answer 3

You could do something like this (DISCLAIMER: I have not checked the laws of the relevant typeclasses, and the presence of a string in the constructor for the exception in Alternative makes me wonder if it is lawful). Scala's heterogeneous andThen is covered by fmap; its homogeneous andThen / compose are covered by the >>> / <<< from Category; orElse is covered by <|>; lift is runToMaybe.

However, without a deep compiler integration such as exists in Scala, the pattern incompleteness warnings will interact poorly with this. Haskell only has module-level pragmas for these things, and you won't want to just indiscriminately turn them off in any module where you declare inexhaustive functions, or you may get nasty surprises. Depending on your usecase, you may find optics more idiomatic and less problematic; you can have the boilerplate generated for you through Template Haskell.

(Note: I called it Inexhaustive because PartialFunction is something of a misnomer, in that it implies that Function is total. But Scala has no termination or positivity checkers, so the compiler is not actually able to talk about totality; so you get this weird situation where a function that is not a partial function is just a "regular" Function, whereas you should be able to call it a "total Function". The question here is not partially or totality, which is a broader idea, but inexhaustivity of pattern matches.)

{-# LANGUAGE TypeApplications #-}
module Inexhaustive
  ( Inexhaustive, inexhaustive
  , runToMaybe, isDefinedAt
  ) where

import Prelude hiding ((.), id)
import Control.Applicative
import Control.Exception
import Control.Category
import Data.Maybe
import System.IO.Unsafe (unsafePerformIO)

newtype Inexhaustive a b = Inexhaustive (a -> b)

inexhaustive :: (a -> b) -> Inexhaustive a b
inexhaustive = Inexhaustive

runToMaybe :: Inexhaustive a b -> a -> Maybe b
runToMaybe (Inexhaustive f) x =
  let io = fmap Just $ evaluate $ f x
  in unsafePerformIO $ catch @PatternMatchFail io (\_ -> return Nothing)

isDefinedAt :: Inexhaustive a b -> a -> Bool
isDefinedAt f = isJust . runToMaybe f

instance Functor (Inexhaustive z) where
  fmap f (Inexhaustive g) = inexhaustive (f . g)

instance Applicative (Inexhaustive z) where
  pure x = inexhaustive (const x)
  (Inexhaustive zab) <*> (Inexhaustive za) = Inexhaustive (\z -> zab z $ za z)

instance Alternative (Inexhaustive z) where
  empty = inexhaustive (\_ -> throw $ PatternMatchFail "inexhaustive empty")
  f <|> g =
    inexhaustive $ \x ->
      case runToMaybe f x <|> runToMaybe g x of
        Just y -> y

instance Category Inexhaustive where
  id = inexhaustive id
  (Inexhaustive f) . (Inexhaustive g) = Inexhaustive (f . g)

Ramer

You might also like spoon. – Hairline