Can any partial function be converted to a total version in Haskell?-CodePudding

So far I have seen numerous "Maybe" versions of certain partial functions that would potentially result in ⊥, like readMaybe for read and listToMaybe for head; sometimes I wonder if we can generalise the idea and work out such a function safe :: (a -> b) -> (a -> Maybe b) to convert any partial function into their safer total alternative that returns Nothing on any instances where error stack would have been called in the original function. As till now I have not found a way to implement such safe function or existing implementations of a similar kind, and I come to doubt if this idea is truly viable.

CodePudding user response：

There are two kinds of bottom actually, non-termination and error. You cannot catch non-termination, for obvious reasons, but you can catch errors. Here is a quickly thrown-together version (I am not an expert so there are probably better ways)

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Exception
import System.IO.Unsafe

safe f = unsafePerformIO $ do
  z <- try (evaluate f)
  let r = case z of
     Left (e::SomeException) -> Nothing
     Right k -> Just k
  return r

Here are some examples

*Main > safe (head [42]) 
Just 42
*Main > safe (head []) 
Nothing
*Main λ safe (1 `div` 0)
Nothing
*Main λ safe (1 `div` 2)
Just 0

CodePudding user response：

No, it's not possible. It violates a property called "monotonicity", which says that a value cannot become more defined as you process it. You can't branch on bottoms - attempting to process one always results in bottom.

Or at least, that's all true of the domain theory Haskell evaluation is based on. But Haskell has a few extra features domain theory doesn't... Like executing IO actions being a different thing than evaluation, and unsafePerformIO letting you hide execution inside evaluation. The spoon library packages all of these ideas together as well as can be done. It's not perfect. It has holes, because this isn't something you're supposed to be able to do. But it does the job in a bunch of common cases.

CodePudding user response：

Consider the function

collatz :: Integer -> ()
collatz 1 = ()
collatz n
 | even n     = collatz $ n`div`2
 | otherwise  = collatz $ 3*n   1

^{(Let's pretend Integer is the type of positive whole numbers for simplicity)}

Is this a total function? Nobody knows! For all we know, it could be total, so your proposed safe-guard can't ever yield Nothing. But neither has anybody found a proof that it is total, so if safe just always gives back Just (collatz n) then this may still be only partial.