Archive for the 'Programming' Category

Monad Exercises in Scala (addendum)

Saturday, April 3rd, 2010

Following is a test harness that should print a series of PASS when executed against a correct solution to the original Monad Exercises in Scala. These exercises include a Haskell version and a test harness for this is also found below.

I have also written a complete solution in Scala and same again for Haskell (clicking either link will give away the answer).

object Main {
  def main(args: Array[String]) {
    import Monad._
    import MonadicFunctions._
 
    val plusOne = Inter(1+)
    val multTwo = Inter(2*)
    val squared = Inter(n => n*n)
    val plus = (_: Int) + (_: Int)
 
    val values = List(
// sequence
sequence(List(List(1, 2), List(3, 4)), ListMonad),
sequence(List(Some(7), Some(8), Some(9)), OptionMonad),
sequence(List(Some(7), None, Some(9)), OptionMonad),
sequence(List(plusOne, multTwo, squared), InterMonad) f 7,
sequence(List(Identity(7), Identity(4)), IdentityMonad),
// fmap
fmap(List(1, 2, 3), (x: Int) => x * 10, ListMonad),
fmap(Some(8), (x: Int) => x * 10, OptionMonad),
fmap(None: Option[Int], (x: Int) => x * 10, OptionMonad),
fmap(plusOne, (x: Int) => x * 10, InterMonad) f 7,
fmap(Identity(9), (x: Int) => x * 10, IdentityMonad),
// flatten
flatten(List(List(1, 2), List(3, 4)), ListMonad),
flatten(Some(Some(8)), OptionMonad),
flatten(Some(None: Option[Int]), OptionMonad),
flatten(None: Option[Option[Int]], OptionMonad),
flatten(Inter(a => Inter(a *)), InterMonad) f 7,
flatten(Identity(Identity(8)), IdentityMonad),
// apply
apply(List((a: Int) => a + 1,
           (a: Int) => a * 2,
           (a: Int) => a % 2), List(1, 2, 3), ListMonad),
apply(Some((a: Int) => a + 1), Some(8), OptionMonad),
apply(None: Option[Int => Int], Some(8), OptionMonad),
apply(Some((a: Int) => a + 1), None: Option[Int], OptionMonad),
apply(Inter(a => (b: Int) => a * b), Inter(1+), InterMonad) f 7,
apply(Identity((a: Int) => a + 1), Identity(7), IdentityMonad),
// filterM
filterM((a: Int) => List(a > 2, a % 2 == 0), List(1, 2, 3), ListMonad),
filterM((a: Int) => Some(a > 1), List(1, 2, 3), OptionMonad),
filterM((a: Int) => Inter(n => a * n % 2 == 0),
  List(1, 2, 3), InterMonad) f 7,
filterM((a: Int) => Identity(a > 1), List(1, 2, 3), IdentityMonad),
// replicateM
replicateM(2, List(7, 8), ListMonad),
replicateM(2, Some(7), OptionMonad),
replicateM(2, plusOne, InterMonad) f 7,
replicateM(2, Identity(6), IdentityMonad),
// lift2
lift2(plus, List(1, 2), List(3, 4), ListMonad),
lift2(plus, Some(7), Some(8), OptionMonad),
lift2(plus, Some(7), None: Option[Int], OptionMonad),
lift2(plus, None: Option[Int], Some(8), OptionMonad)
    )
 
    val verify = List(
// sequence
List(List(1, 3), List(1, 4), List(2, 3), List(2, 4)),
Some(List(7, 8, 9)),
None,
List(8, 14, 49),
Identity(List(7, 4)),
// fmap
List(10, 20, 30),
Some(80),
None,
80,
Identity(90),
// flatten
List(1, 2, 3, 4),
Some(8),
None,
None,
49,
Identity(8),
// apply
List(2, 3, 4, 2, 4, 6, 1, 0, 1),
Some(9),
None,
None,
56,
Identity(8),
// filterM
List(List(3), Nil, List(2, 3), List(2), List(3),
  Nil, List(2, 3), List(2)),
Some(List(2, 3)),
List(2),
Identity(List(2, 3)),
// replicateM
List(List(7, 7), List(7, 8), List(8, 7), List(8, 8)),
Some(List(7, 7)),
List(8, 8),
Identity(List(6, 6)),
// lift2
List(4, 5, 5, 6),
Some(15),
None,
None
)
 
    for((a, b) <- values zip verify)    
      println(if(a == b) "PASS"
              else "FAIL. Expected: " + b + " Actual: " + a)
  }
}

Haskell main function which should print a series of PASS when executed against the original Monad Exercises in Scala.

main :: IO ()
main =
  let plusOne = Inter (1+)
      multTwo = Inter (2*)
      squared = Inter (\n -> n*n)
      s x = show x
      (%) = f
      values =
        [
        -- sequence'
        s (sequence' [[1, 2], [3, 4]] listMonad),
        s (sequence' [Just 7, Just 8, Just 9] maybeMonad),
        s (sequence' [Just 7, Nothing, Nothing] maybeMonad),
        s (sequence' [plusOne, multTwo, squared] interMonad % 7),
        s (sequence' [Identity 7, Identity 4] identityMonad),
        -- fmap'
        s (fmap' [1..3] (*10) listMonad),
        s (fmap' (Just 8) (*10) maybeMonad),
        s (fmap' Nothing (*10) maybeMonad),
        s (fmap' plusOne (*10) interMonad % 7),
        s (fmap' (Identity 9) (*10) identityMonad),
        -- flatten
        s (flatten [[1, 2], [3, 4]] listMonad),
        s (flatten (Just (Just 8)) maybeMonad),
        s (flatten (Just (Nothing :: Maybe Int)) maybeMonad),
        s (flatten (Nothing :: Maybe (Maybe Int)) maybeMonad),
        s (flatten (Inter (Inter . (*))) interMonad % 7),
        s (flatten (Identity (Identity 8)) identityMonad),
        -- apply
        s (apply [(+1), (*2), (`mod` 2)] [1..3] listMonad),
        s (apply (Just (+1)) (Just 8) maybeMonad),
        s (apply (Nothing :: Maybe (Int -> Int)) (Just 8) maybeMonad),
        s (apply (Just (+1)) (Nothing :: Maybe Int) maybeMonad),
        s (apply (Inter (*)) (Inter (1+)) interMonad % 7),
        s (apply (Identity (+1)) (Identity 7) identityMonad),
        -- filterM'
        s (filterM' (\a -> [a > 2, a `mod` 2 == 0]) [1..3] listMonad),
        s (filterM' (\a -> Just (a > 1)) [1..3] maybeMonad),
        s (filterM' (\a -> Inter (\n -> a * n `mod` 2 == 0)) [1..3]
          interMonad % 7),
        s (filterM' (Identity . (>1)) [1..3] identityMonad),
        -- replicateM'
        s (replicateM' 2 [7, 8] listMonad),
        s (replicateM' 2 (Just 7) maybeMonad),
        s (replicateM' 2 plusOne interMonad % 7),
        s (replicateM' 2 (Identity 6) identityMonad),
        -- lift2
        s (lift2 (+) [1, 2] [3, 4] listMonad),
        s (lift2 (+) (Just 7) (Just 8) maybeMonad),
        s (lift2 (+) (Just 7) (Nothing :: Maybe Int) maybeMonad),
        s (lift2 (+) (Nothing :: Maybe Int) (Just 8) maybeMonad)
        ]
      verify =
        [
        -- sequence'
        s ([[1, 3], [1, 4], [2, 3], [2, 4]]),
        s (Just [7..9]),
        s (Nothing :: Maybe Int),
        s [8, 14, 49],
        s (Identity [7, 4]),
        -- fmap'
        s [10, 20, 30],
        s (Just 80),
        s (Nothing :: Maybe Int),
        s 80,
        s (Identity 90),
        -- flatten
        s [1..4],
        s (Just 8),
        s (Nothing :: Maybe Int),
        s (Nothing :: Maybe Int),
        s 49,
        s (Identity 8),
        -- apply
        s [2, 3, 4, 2, 4, 6, 1, 0, 1],
        s (Just 9),
        s (Nothing :: Maybe Int),
        s (Nothing :: Maybe Int),
        s 56,
        s (Identity 8),
        -- filterM'
        s [[3], [], [2, 3], [2], [3], [], [2, 3], [2]],
        s (Just [2, 3]),
        s [2],
        s (Identity [2, 3]),
        -- replicateM
        s [[7, 7], [7, 8], [8, 7], [8, 8]],
        s (Just [7, 7]),
        s [8, 8],
        s (Identity [6, 6]),
        -- lift2
        s [4, 5, 5, 6],
        s (Just 15),
        s (Nothing :: Maybe Int),
        s (Nothing :: Maybe Int)
        ]
  in mapM_
      (\(a, b) ->
        print(if a == b
                then "PASS"
                else "FAIL. Expected: " ++ b ++ " Actual: " ++ a))
      (values `zip` verify)

Type-classes are nothing like interfaces

Friday, April 2nd, 2010

A beginner is confused about Haskell’s type-classes and so asks the question, “What is a type-class?” The response is often devastating, “You know, like Java or C# interfaces.” This wildly misleading statement can leave the beginner in a state of disrepair. I’ll tell you why but first I must emphasise.

Type-classes are nothing like interfaces (emphasis on nothing).

Haskell has something like interfaces. They are called data types and are expressed using the data or newtype keywords. Languages like Java/C# have nothing like type-classes; there is not even a close analogy. Consider for example, Java’s Comparator interface. We would express this in Haskell like so:

newtype Comparator a = C { compare :: a -> a -> Int }

Then if we wanted to sort a list, the type would be sort :: Comparator a -> [a] -> [a]. Notice the explicit passing of the Comparator that would be required at the call site. This is just like Java.

Now suppose we did something that Java cannot do. We used a type-class.

class Comparator a where
  compare :: a -> a -> Int

The type for sorting a list now becomes sort :: Comparator a => [a] -> [a]. This is just like the previous signature except for the way the left-most arrow is written. This is an important distinction. When the caller uses this function, it implicitly passes the Comparator. Also, the type-class instance is decoupled from the data type. These are essential properties of type-classes. Indeed, it is its single-most defining property and since Java/C# have nothing like this, then it has nothing like type-classes.

Scala has implicit parameters which give you the ability to implement the essential property of type-classes (and more). Therefore, Scala does have something very much like type-classes. This is evident in a library such as Scalaz.

But let’s try to save the idea.

Java has implicit type-conversion by virtue of inheritance. For example, a method that accepts a T can be passed a U and its implicit conversion to a T is denoted by the way of U extends T. Notice that no side-effect can be performed during this conversion. This is unlike Scala’s implicit where it’s simply a bad idea, not enforced (Scala also has inheritance like Java).

So, if you are to say type-classes are like anything in these languages, it’s sort-of-like-yeah-ok-not-really inheritance. However, I’m sure you’ll agree, this will only cause confusion for the poor beginner, so it’s best not to draw the analogy at all.

Type-classes are a new concept to people coming from Java/C#. It is most appropriate to explain it as a new concept. I often use the contention between using java.util.Comparable, where the caller has the convenience of implicitly pass the implementation by way of inheritance but inconvenience of carrying the implementation with the data type versus using java.util.Comparator where the caller has the convenience of decoupling the implementation from the data type but requiring explicit passing at the call site. Type-classes (and Scala implicits) resolve this contention with a new concept.

What Does Functional Programming Mean?

Wednesday, March 31st, 2010

Here are some slides to a short talk I gave a few weeks ago.

Hoping to get less ridiculous (i.e. more insightful) blog comments…

Scalaz IRC

Saturday, March 27th, 2010

Scalaz now has an IRC channel.

irc://irc.freenode.net/#scalaz

Monad exercises in Scala

Thursday, March 25th, 2010

A result of discussion in the #scala IRC channel.

A colleague has asked me to convert this to Haskell, which I have done below.

  • The trait Monad answers the question “What does monad mean?”
  • The object Monad answers the question “What are some examples?”
  • The object MonadicFunctions answers the question “What are the practical implications?”

If there are any questions or you get stuck, the #scala or #scalaz channel on Freenode could help out.

// 1. Start here. Observe this trait
trait Monad[M[_]] {
  def flatMap[A, B](a: M[A], f: A => M[B]): M[B]
  def unital[A](a: A): M[A]
}
 
// A simple data type, which turns out to satisfy the above trait
case class Inter[A](f: Int => A)
 
// So does this.
case class Identity[A](a: A)
 
// Monad implementations
object Monad {
  // 2. Replace error("todo") with an implementation
  def ListMonad: Monad[List] = error("todo")
 
  // 3. Replace error("todo") with an implementation
  def OptionMonad: Monad[Option] = error("todo")
 
  // 4. Replace error("todo") with an implementation
  def InterMonad: Monad[Inter] = error("todo")
 
  // 5. Replace error("todo") with an implementation
  def IdentityMonad: Monad[Identity] = error("todo")
}
 
object MonadicFunctions {
  // 6. Replace error("todo") with an implementation
  def sequence[M[_], A](as: List[M[A]], m: Monad[M]): M[List[A]] =
    error("todo")
 
  // 7. Replace error("todo") with an implementation
  def fmap[M[_], A, B](a: M[A], f: A => B, m: Monad[M]): M[B] =
    error("todo")
 
  // 8. Replace error("todo") with an implementation
  def flatten[M[_], A](a: M[M[A]], m: Monad[M]): M[A] =
    error("todo")
 
  // 9. Replace error("todo") with an implementation
  def apply[M[_], A, B](f: M[A => B], a: M[A], m: Monad[M]): M[B] =
    error("todo")
 
  // 10. Replace error("todo") with an implementation
  def filterM[M[_], A](f: A => M[Boolean], as: List[A]
    , m: Monad[M]): M[List[A]] =
    error("todo")
 
  // 11. Replace error("todo") with an implementation
  def replicateM[M[_], A](n: Int, a: M[A], m: Monad[M]): M[List[A]] =
    error("todo: flatMap n times to produce a list")
 
  // 12. Replace error("todo") with an implementation
  def lift2[M[_], A, B, C](f: (A, B) => C, a: M[A], b: M[B]
    , m: Monad[M]): M[C] =
    error("todo")
 
  // lift3, lift4, etc. Interesting question: Can we have liftN?
}

Haskell

  • The data Monad' answers the question “What does monad mean?”
  • The functions under *** Monad implementations *** answers the question “What are some examples?”
  • The functions under *** Monadic Functions *** answers the question “What are the practical implications?”
{-# LANGUAGE RankNTypes #-}
 
-- 1. Start here. Observe this data type
data Monad' m = Monad' {
  unital :: forall a. a -> m a,
  flatMap :: forall a b. m a -> (a -> m b) -> m b
}
 
-- A simple data type, which turns out to satisfy the above trait
newtype Inter a = Inter { f :: Int -> a }
 
-- So does this.
newtype Identity a = Identity { a :: a }
  deriving Show
 
-- *** Monad implementations ***
 
-- 2. Replace error "todo" with an implementation
listMonad :: Monad' []
listMonad = error "todo"
 
-- 3. Replace error "todo" with an implementation
maybeMonad :: Monad' Maybe
maybeMonad = error "todo"
 
-- 4. Replace error "todo" with an implementation
interMonad :: Monad' Inter
interMonad = error "todo"
 
-- 5. Replace error "todo" with an implementation
identityMonad :: Monad' Identity
identityMonad = error "todo"
 
-- *** Monadic functions ***
 
-- 6. Replace error "todo" with an implementation
sequence' :: [m a] -> Monad' m -> m [a]
sequence' = error "todo"
 
-- 7. Replace error "todo" with an implementation
fmap' :: m a -> (a -> b) -> Monad' m -> m b
fmap' = error "todo"
 
-- 8. Replace error "todo" with an implementation
flatten :: m (m a) -> Monad' m -> m a
flatten = error "todo"
 
-- 9. Replace error "todo" with an implementation
apply :: m (a -> b) -> m a -> Monad' m -> m b
apply = error "todo"
 
-- 10. Replace error "todo" with an implementation
filterM' :: (a -> m Bool) -> [a] -> Monad' m -> m [a]
filterM' = error "todo"
 
-- 11. Replace error "todo" with an implementation
replicateM' :: Int -> m a -> Monad' m -> m [a]
replicateM' = error "todo: flatMap n times to produce a list"
 
-- 12. Replace error "todo" with an implementation
lift2 :: (a -> b -> c) -> m a -> m b -> Monad' m -> m c
lift2 = error "todo"
 
-- lift3, lift4, etc. Interesting question: Can we have liftN?

Why are there no big applications written using functional languages?

Wednesday, March 24th, 2010

Because there is no such thing as a big application. There is only bigger or smaller. This is a central tenet of functional programming. “Big application” is a euphemism for “My idea of programming does not scale beyond this point.” You don’t realise how much information you give away when you ask this question.

So can we can stop with the piffle and get on with the interesting and important stuff? Ta.

A poke at the essence of functional programming

Wednesday, March 24th, 2010

I used to work for IBM on the Java implementation. I learned the language inside-out. I did all those Sun certifications and other spanky things. I wanted to understand what a lot of people alleged was so special. I didn’t ever find it.

I have found that few people can tell me the answer to this question. If you don’t know the answer, don’t fret; it’s not the important part.

method(s1.charAt(i), s2.charAt(j));

Assuming s1 and s2 are both of the type java.lang.String, then which call to charAt will occur first?

Many people would correctly guess at the left-most one. This is correct and is mandated by the specification.

However, on introspection, the reason nobody really knows is because it doesn’t matter. If the specification implementation had a bug and executed the right-most call first, then we, the programmer, would never even know. We gloss over this every day when we read Java code.

However, does this hold for all functions? What if it was something other than charAt? No, unfortunately, this only holds true for a specific set of functions. The charAt function is referentially transparent. For any given String and any given int then charAt will consistently return the same char. This is true for other referentially transparent functions too, but not any arbitrary function. Imagine if charAt did a database call or something like that!

Let us suppose now a new language feature that enforced the referential transparency of our functions. If it is referentially transparent, the compiler makes sure of it. Now imagine a new language where every function was referentially transparent.

All of a sudden, in the blink of an imagined hypothetical, the explicit order of invocation is no longer important. Just like that, poof, gone.

Welcome to the beginning of an understanding of the essence of functional programming.

Have fun! :)

I have found that…

Tuesday, March 23rd, 2010

I have found that many classes are created for the specific purpose of a sequence function in the ((->) t) monad, particularly in Java, C# and Python. Create a class, with a constructor that takes an argument (t) so that one may call many of its methods, each of which has access to t.

sequence :: [m a] -> m [a]
sequence* :: [t -> a] -> t -> [a]

If we consider the type of t which we shall call Swizzle and the created class we shall call SwizzleManager then

// A constructor accepting a Swizzle
SwizzleManager m = new SwizzleManager(t);
// One of the following usually follow:
//   A list constructed by the results of executing several methods on 'm'
List<R> = { m.a(x), m.b(y), m.c(z) }
//   A loop over a list of the results of executing several methods on 'm'
for(R r : { m.a(x), m.b(y), m.c(z) }) {
  use(r);
}
//   A list of effects to execute using 'm'
m.a(x);
m.b(y);
m.c(z);

Automated Validation with Applicatives and Semigroups (Part 2 - Java)

Sunday, March 21st, 2010

In a previous post, I mentioned a small library for validating using an applicative functor pattern with a semigroup for accumulating errors using Haskell, Scala and Java programming languages. In this post, I will give a set up for an example usage, but not necessarily a complete example. This is left as an exercise and may be elaborated on in a future post.

I will start with Java. First we must decide how we are going to accumulate errors. I have decided to store them in a LinkedList. In more practical languages with a better collections library, we would probably use something else. We will use something else for Scala and Haskell (later!), or you could use the Functional Java extension. In the meantime, we will use java.util.LinkedList. We start by writing its Semigroup implementation:

public static <A> Semigroup<LinkedList<A>> LinkedListSemigroup() {
  return new Semigroup<LinkedList<A>>() {
    public LinkedList<A> append(final LinkedList<A> a1,
                                final LinkedList<A> a2) {
      final LinkedList<A> r = new LinkedList<A>(a1);
      r.addAll(a2);
      return r;
    }
  };
}

This is very straight-forward. In the previous example, I mentioned a class Person that is made of an age and a name. The age is an integer between 0 and 130 while the name is any string that starts with an upper-case character. Let’s write these data types:

// int wrapper between 0 and 130
class Age {
  private final int i;
  private Age(final int i) { this.i = i; }
  public int value() { return i; }
  public static Age age(final int i) {
    if(i <= 0 || i >= 130)
      throw new Error("out of range");
    else
      return new Age(i);
  }
}

And here is Name:

// String wrapper starts with upper-case
class Name {
  private final String s;
  private Name(final String s) { this.s = s; }
  public String value() { return s; }
  public static Name name(final String s) {
    if(s.isEmpty() || !Character.isUpperCase(s.charAt(0)))
      throw new java.lang.Error();
    else
      return new Name(s);
  }
}

I won’t bother writing the Person data type, but it is sufficient to say it will have an Age field and a Name field.

Now for validation. Suppose we have two string values; one each for age and name. We would like to check these for validation and return either one or more error messages (String) or a Person. More succinctly, we want a function with the type:

String -> String -> Validation<LinkedList<String>, Person>>

How are we going to achieve this function? First we must say how to create an Age from a String or an error message if we cannot:

String -> Validation<LinkedList<String>, Age>>

and same for Name

String -> Validation<LinkedList<String, Name>>

We also need a function to create a Person from an Age and a Name

Age -> Name -> Person

This is simple. It’s the Person constructor.

So to sum up, we need to write a function with this type:

Arguments:

  •   F<String, Validation<LinkedList<String>, Age>>>
  •   F<String, Validation<LinkedList<String>, Name>>>
  •   F<Age, F<Name, Person>>
  •   Semigroup<LinkedList<String>>

Return type:

F<String, F<String, <Validation<LinkedList<String>, Person>>>>

Of course such a function is likely to be polymorphic, rather than specifying concrete types. I recommend starting by writing a function with this type:

Arguments:

  •   F<T, F<U, V>>
  •   F<A, Validation<E, T>>
  •   F<B, Validation<E, U>>

Return type:

F<A, F<B, Validation<E, V>>

This function can be written by using the constructs mentioned in the previous post. I’m out of breath. Java is incredibly laborious.

Scala and Haskell for another time!

Automated Validation with Applicatives and Semigroups (for Sanjiv)

Sunday, March 21st, 2010

Sanjiv is an ex-colleague of mine who recently gave an excellent presentation at Brisbane Functional Programming Group. His presentation was on the use of the disjoint union algebraic data type for representing error handling or “validation”. This data type is often called Either. Sanjiv used the Scala version for his presentation.

Here I am going to write a data type that is just like (isomorphic to) Either called Validation. There will be two constructors for failure and success. I will be using Haskell, Scala and Java. I am going to present a function that is mentioned in an excellent paper called Applicative Programming with Effects.

There is a slight difference in my implementation to the function in this paper. The one mentioned in the paper uses a Monoid constraint, while I am using the more general Semigroup. This allows data types that are semigroups but not monoids (all monoids are semigroups). In particular, a non-empty list is a semigroup but not a monoid.

This constraint on the failing value allows the user to automatically accumulate errors as they chain through the Validation values, for example, by keeping them in a non-empty list. I am not going to give example usages of this code in this post because I think it is a great exercise for others and I do not want to spoil it. It is sufficient to say that any usage that type-checks is likely to be a useful example. I may give examples in the future if there is some confusion that needs clarification.

The function can accumulate Validation values using the applicative programming pattern. If all given are successful, you’ll be left with a function that takes all the successful values to a new value, which will be returned as a success. If at least one is not successful, the applicative pattern will begin accumulating with that error value and any future values.

I recommend starting with a simple example such as a Person type with an age :: Int and name :: String with imposed validation rules such as “age must be above 0 and less than 130″ and “name must start with a capital letter”. The applied function at the end should be ValidatedInt -> ValidatedString -> Person.

Like I said, if there is any confusion, I’ll expand later. Put the questions in the comments. Enjoy! :)

Here is a Haskell implementation of this:

data Validation e a = Fail e | Success a deriving (Eq, Show)
 
-- Associative, binary operation (Monoid without identity)
class Semigroup a where
  append :: a -> a -> a
 
(<+>) :: Validation e a -> (a -> b) -> Validation e b
Fail e <+> _ = Fail e
Success a <+> f = Success (f a)
 
(<*>) :: (Semigroup e) => Validation e a
    -> Validation e (a -> b)
    -> Validation e b
Fail e1 <*> Fail e2 = Fail (e1 `append` e2)
Fail e1 <*> Success _ = Fail e1
Success _ <*> Fail e2 = Fail e2
Success a <*> Success f = Success (f a)

And Scala:

sealed trait Validation[E, A] {
  def <+>[B](f: A => B): Validation[E, B] = this match {
    case Fail(e) => Fail(e)
    case Success(a) => Success(f(a))
  }
 
  def <*>[B](f: Validation[E, A => B])(implicit s: Semigroup[E])
    : Validation[E, B] = this match {
    case Fail(e1) => f match {
      case Fail(e2) => Fail(s append (e1, e2))
      case Success(_) => Fail(e1)
    }
    case Success(a) => f match {
      case Fail(e2) => Fail(e2)
      case Success(f) => Success(f(a))
    }
  }
}
case class Fail[E, A](e: E) extends Validation[E, A]
case class Success[E, A](a: A) extends Validation[E, A]
 
// Associative binary operation (Monoid without identity)
case class Semigroup[A](append: (A, A) => A)

And now, for the allegedly practical Java. Hold your breath:

// Java pre-amble, sigh.
interface F<X, Y> {
  Y apply(X x);
}
 
// Associative binary operation (Monoid without identity)
interface Semigroup<A> {
  A append(A a1, A a2);
}
 
abstract class Validation<E, A> {
  // No algebraic data types in Java. Use a Church encoding (catamorphism).
  public abstract <X> X fold(F<E, X> fail, F<A, X> success);
 
  // Construction for fail
  public static <E, A> Validation<E, A> fail(final E e) {
    return new Validation<E, A>() {
      public <X> X fold(final F<E, X> fail, final F<A, X> success) {
        return fail.apply(e);
      }
    };
  }
 
  // Construction for success
  public static <E, A> Validation<E, A> success(final A a) {
    return new Validation<E, A>() {
      public <X> X fold(final F<E, X> fail, final F<A, X> success) {
        return success.apply(a);
      }
    };
  }
 
  // <+>
  public <B> Validation<E, B> map(final F<A, B> f) {
    return new Validation<E, B>() {
      public <X> X fold(final F<E, X> fail, final F<B, X> success) {
        return Validation.this.fold(fail, new F<A, X>() {
          public X apply(final A a) {
            return success.apply(f.apply(a));
          }
        });
      }
    };
  }
 
  // <*>
  public <B> Validation<E, B> applicativate(
      final Validation<E, F<A, B>> f,
      final Semigroup<E> s /* no implicits or type-classes in Java */) {
    return Validation.this.fold(new F<E, Validation<E, B>>() {
      public Validation<E, B> apply(final E e1) {
        return f.fold(new F<E, Validation<E, B>>() {
          public Validation<E, B> apply(final E e2) {
            // case (Fail(e1), Fail(e2))
            return Validation.fail(s.append(e1, e2)); 
          }
        }, new F<F<A, B>, Validation<E, B>>() {
          public Validation<E, B> apply(final F<A, B> f) {
            // case (Fail(e1), Success(f))
            return Validation.fail(e1); 
          }
        });
      }
    }, new F<A, Validation<E, B>>() {
      public Validation<E, B> apply(final A a) {
        return f.fold(new F<E, Validation<E, B>>() {
          public Validation<E, B> apply(final E e2) {
            // case (Success(a), Fail(e2))
            return Validation.fail(e2); 
          }
        }, new F<F<A, B>, Validation<E, B>>() {
          public Validation<E, B> apply(final F<A, B> f) {
            // case (Success(a), Success(f))
            return Validation.success(f.apply(a)); 
          }
        });
      }
    });
  }
}