Brilliance of Haskell's Maybe type and the Value of Static Type Checking
moreindirection.blogspot.com
moreindirection.blogspot.com
Here is a relevant paper, "Non-null References by Default in Java: Alleviating the Nullity Annotation Burden":
http://www.springerlink.com/content/f197143t80671627/
"we conducted an empirical study of 5 open source projects (including the Eclipse 3.3 JDT Core) totaling over 700 KLOC. The results allow us to confirm that in Java programs, at least 2/3 of declarations of reference types are meant to be non-null, by design."
Is there a source for that? And has Gosling apologized to the world since then? (I mean Hoare apologized, Gosling should grovel and beg for forgiveness)
Consider a program that takes a leaf-labelled tree of Ints and replaces each int with the maximum found in the whole tree. You can do this in two passes over the tree - one to find the max value, one to re-write the tree.
But you can also do it in a single pass using lazy evaluation:
----------------
data Tree = Branch Tree Tree | Leaf Int
label :: Tree -> Tree
label tree = t2
where (t2,k) = thread tree k
thread (Leaf v) k = (Leaf k, v)
thread (Branch l r) k = (Branch l' r', max lv rv)
where
(l',lv) = thread l k
(r',rv) = thread r k
The idea here is that `thread` runs through the tree replacing the values with some input value `k` and also calculates the max value of the tree. The function `label` then uses the output of thread as its own input.
This all works fine as long as you never look at the value of `k` inside `thread`. If you do, you go into an infinite loop as `k` then depends on itself.
This is similar to `k` being a pointer to an Int that doesn't get initialised until the function `thread` returns. If you examine it before then, you get a null pointer exception.
But those are completely different features, option types don't imply lazy evaluation (and the other way around). OP didn't talk about lazy evaluation once. There might be issues with lazy eval, but that's completely not the subject.
An option type, especially one which allows you to lift operations into it (as Haskell's does) is a much better solution as it gives the programmer the choice of behavior: does he not care and just want to keep his option, or does he want to know and unwrap the value within the container?
Objective-C allows half of this, but it's generally the wrong half.
Most other statically typed languages allow neither solution and are therefore broken.
Just a little nitpicking here. In C# integral types cannot hold null unless explicitly declared nullable [1], ie.
int x = null; // won't compile
int? x = null; // compiles fine, shorthand for Nullable<int> x = null;
[1]: http://msdn.microsoft.com/en-us/library/1t3y8s4s(VS.80).aspx
IIRC, some Java dialects re-introduce the idea of a variable that cannot be null, and it is possible to do fancy tricks with annotations to produce the same effect.
datatype 'a option = NONE | SOME of 'a
Just 1 >> Nothing >> Just 3
=> Nothing
Just 1 >> Just 2 >> Just 3
=> Just 3
data Maybe a = Nothing | Just a
instance Monad Maybe where
[...]
When you use it a bare type, every time in your code you use a Maybe, you have to manually check for Nothing and extract the value in Just. And you can't compose functions involving Maybe without either letting Maybe bleed into the input types of functions where it is not necessary, or writing some clever wrappers (which will probably actually end up defining a monad).
Using Maybe in this way has a common structure:
f :: Maybe a -> Maybe b
f Nothing = Nothing
f (Just x) = Just (do something with x)
wrapMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
wrapMaybe Nothing f = Nothing
wrapMaybe (Just x) f = f x
instance Monad Maybe where
Nothing >>= f = Nothing
(Just x) >>= f = f x
return x = Just x
class Monad m where:
(>>=) :: m a -> (a -> m b) -> m b -- (AKA bind)
return :: a -> m b
What seems trivial with Maybe as a monad is that "return", the other part of defining a monad, is just the data constructor Just, whereas in other monads it's more complicated.
---
EDIT: I had previously defined: (Just x) >>= f = Just (f x) -- this is actually fmap for Maybe, which is also the lifting function I mentioned
[1] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4...
[2] Forgive me, it is at this point that I realize you may actually know all about monads and were just wondering what's monadic about Maybe. But I was already too deep into Writing A Monad Tutorial to throw it away. Incidentally,
NB: I've never actually exposed my tentative understanding of monads in public before, so before trying to follow anything I've said here, wait on someone on surer ground to pipe up with approval (or criticism, which I would very much appreciate).
fmap :: (Functor f) => (a -> b) -> f a -> f b
fmap f (Just x) = Just (f x)
fmap (\x -> x * x) (Just 4)
=> Just 16
lift f = (return . f)
[Edit: It says on Wikipedia that a functor maps a function in one category to a function in another category]
---
You are not, strictly/pedantically speaking, because fmap is the single function that defines a Functor to begin with [1]:
class Functor f where
fmap :: (a -> b) -> f a -> f b
You are right in seeing that fmap is lifting -- liftM, which is defined in terms of just bind and return for Monads, is (I believe... see warning above) identically fmap. fmap = map for Lists as seen as Functors, for example, which lifts a function (a -> b) to ([a] -> [b])... "into" the Functor/Monad, I suppose.
---
[1] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4...
person.andand.occupation.andand.company.andand.billing_address
Person.find(:name => "Bob").andand {|person| person.fire_out_of(cannon) }
x = func(null); // func is ignored and x is null
proc(null); // proc is ignored and an NPE is thrown.
and so implicitly
y = a(b(c(d(null)))); // a b c d are ignored and y == null
This would mean you could treat null like Nothing, threading it through non side effecting functions and only testing the result. If you tried to use it with a side effect, it would halt.
The compiler would be free to omit these checks where x is provably not null. For example:
foo (x);
y = bar(x);
The assignment to y does not need a null check, because a null would have thrown NPE in foo.
Side effect of this design: code will never receive a null in parameters. Parameter values can be assumed to be definitely not-null by coder and compiler alike.
EDIT: one more change would be needed: prim = func(ref) is illegal unless ref can be proved not null. Also, add a no-op built-in, notnull(x) that does nothing except NPE if x is null. That could be used as proof to the compiler.
Acceptable — barely — in dynamically typed languages, but utterly moronic for a strongly typed language where you can make references null-safe statically and at the type level.
Hiding nulls under the carpet is only a recipe for painfully hard to discover bugs in the long run.
www.brics.dk/~hosc/local/LaSC-8-4-pp293-341.pdf
The first 11 pages really helped me understand the motivations for monads and it explains bind and return. It's written really clearly and doesn't assume much prior knowledge. I think it may be the original paper introducing monads to Haskell but I could be wrong.
(For some reason its a .pdf when it should be .ps.gz)
http://research.microsoft.com/en-us/um/people/simonpj/papers...
We could thus expand the type given for runST as follows: runST is a function which, for every instance of the type a, and every instance of the type s, accepts a state transformer (with type ST s a) and returns a value of type a.
If you want to attain a better understanding of the logical concepts and notation used in the article, try getting hold of an introductory logic text. I recommend Enderton's 'A Mathematical Introduction to Logic'.