FunLand: Algebraic("Container") Data Types for Elixir - Prerelease

Been waiting for this. ^.^

EDIT: Going to add an Either/Result that has a left or right type? Usually used in the same vein as Maybe but usually as return values to hold either a success value and result or an error value and reason (equiv to the usual {:ok, something}/{:error, reason}) with the usual map and such helpers on them as well?

Yes, as you can see on the Roadmap (but please do tell if it isn’t clear enough), Either/Result is on there.

Ah, I did see it but I glossed over it as it looked like a function that took two maybe’s and returned the first that was set. Either/Result should not be two things with possible states but rather two possible things. The difference between Either(Maybe a, Maybe b) and Either(a or b) I guess?

@OvermindDL1: You’re right. I dug a bit deeper into the source of Haskell et al, and now I finally understand what Either actually is. It is similar to Maybe, with the difference that the fallback(error, null, etc) value is not static ‘nothing’, but could be anything you like, so you have more information on e.g. at what place something went away from the happy path.

I have released version 0.6 which includes Either. I am not entirely certain about the name Either, though, since I find it somewhat unclear from the name that ‘left’ is thought of as the fallback answer.

I believe that Scala uses ‘Option’ and some other languages use ‘Result’, but these also seem somewhat vague. I am still looking for a better name.

I can’t speak for Scala, but for Rust I can tell that Result<A, B> is similar to Haskells Either a b, while Rusts Option<A> is similar to Haskells Maybe a.

Also even if often done like this, I wouldn’t say that Either is to signal value or error, but signals the possible outcome of a computation. Consider \n -> if n >= 0 then Right n else Left (-n) (Haskell). This example is somewhat constructed but shows that Either is not always about an error.

Thats the reason why there is (in Rust at least) often an additional Error<A>/Error a which does alias to some according Either String a.

Also, even if it is common and idiomatic to use Right for success, this is not necessarily true for every language! Idris does use Either the other way round and uses Left for success (its not common though to use Maybe or Either though).

@NobbZ thank you very much! I am relatively new to algebraic data types myself, and FunLand is created mostly to make it clear to newcomers what these things are. Feedback like this is greatly appreciated.

Yeah I’ve used both Result and Maybe in the same language, where Maybe is basically a 2-element union (actual union types are better, and if the language has actual union types like elm then there is no maybe), and Result is basically the same thing but its two types are usually Ok (right) and Err (left).

You describe ADTs as Containers for some other types, thats not the only truth. ADTs are much more complex.

When introducing ADTs I’d do roughly the following order:

1. Simple enumerations as in data Bool = False | True or data Fruits = Apple | Peach | Orange.
2. Record/Struct Like as in data Person = Person String Date.
3. Replacement for tagged unions as in data NPC = Monster String Int | Merchant String [(Item, Int)].
4. Introduce type-variables as in data Maybe a = Just a | Nothing and explain that this is an extension to the former ones.

ADT itself are not necessary to define classes (Haskell term) or interfaces (Idris term) since they are very similar to what the OO-World does call an interface ever since.

As you can see, ADT is more or less an abstraction of what the C world does know as 3 separate concepts: enum, struct, and (tagged) union.

Can you please elaborate what you mean by “union types are better”?

Also when I compile my stuff to something baremetal, I’d be glad if Maybe would get compiled to some pointer type, where Nothing is represented as NULL. This is called a “zero-cost abstraction”, a buzzword that has been more or less introduced by the Mozilla Foundation and Rust

Well in Elm parlance (since that is what I’ve been doing a lot lately and its syntax is stuck in my head), a Either can only represent two values, which might be fine, however left/right is… not descriptive either (Elm has Maybe on javascript represented as null or the value). Compared to a Union type:

type MyWellTypedMaybe
  = ImAString String
  | ImAnInt Int

Then just use it as ImAString "test" or ImAnInt 42. That is far more descriptive than something like Left "test" or Right 42. You could implement Either in the union types, or you could implement Result (and in fact Elm does implement Result like this):

type Result err suc
  = Err err
  | Ok suc

And you use it like:

myFunc : (Result String Int) -> blah
myFunc res = do stuff

myFunc Ok 42
-- or
myFunc Err "a string"
-- or assign to variables or whatever
let
  a = Ok 42
in
  myFunc a

Proper Tagged Union Types can build up any of those others with ease. I really wish Elixir had a form of Tagged Union types built in, could be done as something like:

defunion UnionName do
  MyType {s:string(), i:int()}
  AnotherType i:int(), when i>3
  MoreType something:map()
end

So imagine defunion being a macro, takes a union name and a do body, the body defines a set of types that the union could be along with names, typespecs, and an optional when clause of what they store. Internally it would just be represented as a normal erlang tagged tuple, so doing something like UnionName.MyType("string", 42) would just return {UnionName.MyType, {"string", 42}} or so. The constructors verify the types are correct and the constraints if any provided. You could then do something like a special unioncase or so:

s = UnionName.AnotherType(42)
a = unioncase UnionName, s, do
  MyType t -> IO.inspect {:mytype, t}
  AnotherType i ->IO.inspect {:anothertype, i}
  MoreType m ->IO.inspect {:moretype, m}
end

And so a would be {:anothertype, 42} in this case. However the important bit would be that unioncase would require the union, access it at compile-time to find out what makes it up, and make sure that all cases are covered, so something like this:

s = UnionName.AnotherType(42)
a = unioncase UnionName, s, do
  MyType t -> IO.inspect {:mytype, t}
  AnotherType i ->IO.inspect {:anothertype, i}
end

Should cause a compile-time warning/error about not all union cases are covered, missing the ‘MoreType’ case, or something like:

s = UnionName.AnotherType(42)
a = unioncase UnionName, s, do
  MyType t -> IO.inspect {:mytype, t}
  AnotherType i, when i>100 ->IO.inspect {:anothertype, i}
  MoreType m ->IO.inspect {:moretype, m}
end

And this would cause a warning/error about something like not all union cases are covered, AnotherType is not covered from i>=3 and i<=100 or so. Of course a _ -> would cover everything.

/me is a huge proponant of good type systems, the only real thing that Erlang is missing for me, the number of times the lack of a type system bites my butt is far far far more than it would take me time to fix the issues to start with by a type system yelling at me.