What is pure function?

What is pure function?

What is pure function? According to Wikipedia:

  1. The function always evaluates the same result value given the same argument value(s). (…)
  2. Evaluation of the result does not cause any semantically observable side effect or output (…).

The first point seems to be clear. It’s a ‘natural’ definition of a mathematical function we learn in the primary school. When can a function yield a different result given the same arguments? Only when it calls impure functions or depends on the external state in the calculations.

The second point mentions semantically observable side effect or output. First of all, what does semantically observed stand for?

Semantics is a branch of science that deals with meaning – a connection between a symbol and something in our senses or mind that the symbol expresses. We associate the word bird with a flying animal covered by feathers. In a Java program, we know that the + symbol stands for addition of numbers or concatenation of strings. Note that this is not the same algebraic operation; numeric addition is commutative, string concatenation is not.

So, for me, semantically observed means (pun intended) being significant in our program.

What is then a side effect? When we modify a global variable, we cause a side effect. Same with calling a setter on an object passed to us. Writing to a file is usually considered a side effect too. Global variables, all living objects during the execution of a program, current content of the filesystem – it’s all state. Side effects are changes to the external state from the perspective of a function that will stay visible after the function is executed.

Let’s see some examples (in ES6). It this function pure?

array => {
  array.reverse();
  // more transformations of the array
}

It uses the Array.reverse method that works in-place. Array object passed to the function is going to be modified – we are changing the external state of the function. Final verdict – we are dealing with an impure function.

Another, slightly modified version of this function:

array => {
  const clone = a => a.slice(0);
  const reversed = clone(array).reverse();
  // more transformations of the array
}

It makes a (shallow) copy of the array argument before mutating it. Assuming that subsequent array transformations are pure, i.e. they don’t mutate the array elements, this function can be considered pure. Seen from the outside, there is no modification of state. array, the only element of the external state known to our function, remains unchanged.

Conclusion

If you want to be pure, don’t get your hands dirty with the outside world:

  • don’t rely on it in your calculations (point 1)
  • don’t try to change it (point 2).

Additional reading

Advertisements

Functional programming open space

Functional programming open space

Open space about functional programming

March 15th. Saturday. 20 geeks. 5 sessions in 1-2 tracks. At Madrid on Rails.

Idea and arrangements

I’m quite interested in functional programming, both theory and practice. The initial idea dates back to 2013, when FP Madrid community was created. I simply wanted to gather during all the day and chatter about FP.

In January 2014 I suggested the idea on a FP Madrid meetup. Initial feedback was encouraging, so I chose a date (March 15th) and a venue (Madrid on Rails). By the way, it is hard to find a venue that is: 1. within Madrid city limits, 2. free, 3. open on Saturdays, 4. and open all day.

A week before the scheduled date I got the final confirmation from Estela from Madrid Emprende. I started up the marketing machine – spamming local communities and dusting off my Twitter account. The company I work for, Osoco, provided us with a delicious breakfast (big thank you!). Friday night before the event there was 35 confirmed attendees.

D-Day

marketplace

Finally about 20 fellow programmers made it to the meeting. We started by with the typical introduction about open space principles and rules. After explaining how the schedule was going to be built, there was a round of topic proposals. We filled three tracks, five sessions each. Not a bad result for twenty person group. Though many topics died a natural death due to lack of participants.

Although I facilitated the meeting, I had enough time and energy to attend all sessions of my interest:

  • Intro to Haskell – we went over basic Haskell syntax which I’m still getting used to.

  • Web applications using functional approach – I arrived quite late (we were continuing the Haskell session around the coffee table) and missed the most of discussion. What I proposed was to sketch some Clojure code implementing business logic of some imaginary use cases.

Intro to Haskell

  • Java 8 lambdas – fail; we wanted to do a kata with lambdas. Nobody had JDK8 installed and it was impossible to download it.

  • DDD in Clojure (or in another functional language) – we went through two basic use cases (creation and modification) and wrote some code implementing it with DDD patterns. I felt confused, because I associate DDD with objects having data and behaviour. In Clojure you separate those two into dumb data structures (maps) and functions performing business operations on them (and returning copies of modified data).

  • Category theory – I felt like having a theoretical session about category theory. I struggle to understand it and I wanted to get some tangible examples of categories, arrows and so on. It seemed that everyone was equally confused as me. The conversation shifted to algebraic structures and their counterparts in Haskell. Another question raised was: “do I have to understand all the theory behind functional programming and to be a proficient functional programmer”?

Wrap-up and retrospective

Good open space should close with wrap-up and retrospective. What did we enjoy (or not)? What can be improved in case we, as the community, want to repeat this event?

We did two rounds: personal reflections and a perfection game. Here is the summary of feedback we gathered (I hope I’m not missing any important point):

  • Open the idea marketplace before the event (using a wiki or a more sophisticated tool like Ideascale). It would allow to have more prepared sessions.

  • Not all sessions were run because lack of interest. Voting system with stickers and a reduced number of tracks would have filtered out such sessions.

  • Representations from many communities – FP is a cross cutting paradigm, implemented to lesser or greater extent in a lot of languages. Different backgrounds yield diverse points of view, which enrich discussions.

  • Some more experiences functional programmers expected more engagement from novices (questions, doubts, requests for introductory tutorials). Both parties learn. And this is the purpose of an open space.

  • More facilitation to break the ice at the beginning (I’m the culprit, I was my first facilitation :))

  • Drowsiness after lunch. Maybe we should reduce the duration and finish before (late lunch) – e.g. 9:30 – 14:30 with 4 sessions?

Overall, it was a grateful and enlightening experience for all who sacrificed their Saturday and me as participant and facilitator.

Thanks to

Android form conversion and validation with Option monad

What I want to do

  • Given a form in an Android activity or dialog, convert form values (java.lang.Strings) to domain classes and validate if they fulfill business constraints
  • Don’t validate if there is a conversion error
  • Chain validators
  • Perform complex validations (e.g. of two dependent fields)

Solution with Option monad

I encapsulated a form value coming from a visual component (it can be an EditText, Spinner, whatever) in the FormValue monadic type. This is a straight implementation of the Option monad with two subtypes:

  • Some containing the valid value
  • None containing the error description

See the source code below for the implementation:

public abstract class FormValue<T> {
    public static <T> FormValue<T> some(T value) {
        return new Some(value);
    }

    public static <T> FormValue<T> none(String error) {
        return new None(error);
    }

    private FormValue() {}

    public abstract boolean hasValue();
    public abstract T value();

    public abstract boolean hasError();
    public abstract String error();

    public abstract FormValue<T> validateWith(Validator<T> validator);

    public static class Some<T> extends FormValue<T> {
        private T value;

        private Some(T value) { this.value = value; }

        @Override
        public boolean hasValue() { return true; }
        @Override
        public T value() { return value; }

        @Override
        public boolean hasError() { return false; }
        @Override
        public String error() {
            throw new NotImplementedException("Not an error");
        }

        @Override
        public FormValue<T> validateWith(Validator<T> validator) {
            return validator.validate(value);
        }
    }

    public static class None<T> extends FormValue<T> {
        private String error;

        private None(String error) { this.error = error; }

        @Override
        public boolean hasValue() { return false; }
        @Override
        public T value() {
            throw new NotImplementedException("Not a value");
        }

        @Override
        public boolean hasError() { return true; }
        @Override
        public String error() { return error; }

        @Override
        public FormValue<T> validateWith(Validator<T> validator) {
            return this;
        }
    }
}

How does it work?

Conversion

First, we have to extract the raw value stored in a widget and convert it to a domain representation wrapped in FormValue. We do this with the ViewValueExtractor interface:

public interface ViewValueExtractor<T> {
    ViewValueExtractor<T> withMessage(String message);

    FormValue<T> extractValue();
}

Implementations of this interface depend on the widget. In the simplest form, it extracts a String value from a TextView doing no conversion (and thus not raising any errors):

public class StringExtractor implements ViewValueExtractor<String> {
    private TextView view;

    public StringExtractor(TextView view) { this.view = view; }

    public ViewValueExtractor<String> withMessage(String message) {
        return this;
    }

    public FormValue<String> extractValue() {
        return FormValue.some(view.getText().toString());
    }
}

Another example converts a text field to the SSN class, requiring AAA-GG-SSSS format:

public class SSN {
    // getters and setters omitted for brevity
    public int areaNumber;
    public int groupNumber;
    public int serialNumber;

    public SSN(int areaNumber, int groupNumber, int serialNumber) {
        this.areaNumber = areaNumber;
        this.groupNumber = groupNumber;
        this.serialNumber = serialNumber;
    }
}

public class SSNExtractor implements ViewValueExtractor<SSN> {
    private TextView view;
    private String message;

    public SSNExtractor(TextView view) {
        this.view = view;
    }

    public ViewValueExtractor<SSN> withMessage(String message) {
        this.message = message;
        return this;
    }

    public FormValue<SSN> extractValue() {
        String text = view.getText().toString();
        String[] ssnParts = text.split("-");
        if (ssnParts.length != 3) {
            return FormValue.none(message);
        }
        try {
            return FormValue.some(
                new SSN(
                    Integer.valueOf(ssnParts[0]), 
                    Integer.valueOf(ssnParts[1]), 
                    Integer.valueOf(ssnParts[2])
                )
            );
        } catch (NumberFormatException e) {
            return FormValue.none(message);
        }
    }
}

Generally speaking, you need to provide some way to pull out the value from a visual component and turn it into Some if the conversion was successful or None (with an error message).

Validation

We have already an object representing a value from our solution domain; now it’s time to validate it. We do it implementing a Validator:

public interface Validator<T> {
    Validator<T> withMessage(String message);

    FormValue<T> validate(T value);
}

It can be a generic validator:

public class GreaterThatOrEqualValidator<T extends Comparable<T>> implements Validator<T> {
    private T minValue;
    private String message;

    GreaterThatOrEqualValidator(T minValue) {
        this.minValue = minValue;
    }

    public Validator<T> withMessage(String message) {
        this.message = message;
        return this;
    }

    public FormValue<T> validate(T value) {
        if (value.compareTo(minValue) >= 0) {
            return FormValue.some(value);
        }

        return FormValue.none(message);
    }
}

Or a domain-specific validator, e.g. for our Social Security Number:

public class SSNValidator implements Validator<SSN> {
    private String message;

    public Validator<SSN> withMessage(String message) {
        this.message = message;
        return this;
    }

    public FormValue<SSN> validate(SSN value) {
        if (areaValid(value.areaNumber) 
            && groupValid(value.groupNumber) 
            && serialValid(value.serialNumber)) {
            return FormValue.some(value);
        }

        return FormValue.none(message);
    }

    private boolean areaValid(int areaNumber) {
        return areaNumber >= 0 && areaNumber <= 999;
    }

    private boolean groupValid(int groupNumber) {
        return groupNumber > 0 && groupNumber <= 99;
    }

    private boolean serialValid(int serialNumber) {
        return serialNumber > 0 && serialNumber <= 9999;
    }
}

If you go back to the implementation of FormValue.validateWith, you may notice that Validator.validate will be called only for Some value. In case of None (resulting e.g. from a wrong conversion), validateWith returns the same None object.

Complete example – conversion + validation

We convert the SSN field to SSN and check if it’s valid. In case of errors (during conversion or validation), an error message will be displayed in a Toast.

public class MonadicValidatorDemoActivity extends Activity {
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);

        findViewById(R.id.validate).setOnClickListener(
            new View.OnClickListener() {
                public void onClick(View v) {
                    validateForm();
                }
            }
        );
    }

    private void validateForm() {
        TextView ssnField = (TextView) findViewById(R.id.ssn);
        String wrongSSNFormatMsg = getString(R.string.wrongSSNFormat);
        String invalidSSNMsg = getString(R.string.invalidSSN);
        
        FormValue<SSN> ssn = new SSNExtractor(ssnField).withMessage(wrongSSNFormatMsg)
            .extractValue()
            .validateWith(new SSNValidator().withMessage(invalidSSNMsg));

        if (ssn.hasValue()) {
            Toast.makeText(this, "SSN: " + ssn.value(), Toast.LENGTH_LONG).show();
        } else {
            Toast.makeText(this, "Error: " + ssn.error(), Toast.LENGTH_LONG).show();
        }
    }
}

Chained and dependent validation

You can combine validators, adding more validateWith calls. Dependent validation is also possible:

  • either by implementing a validator factory accepting a FormValue and implementing a no-op or identity validator (NoOpValidator) – see the code example below
  • or by implementing a Validator verifying a FormValue, e.g. GreaterThatOrEqualValidator<T extends Comparable> implements Validator<FormValue>
private void validateForm() {
    // Field and message finders omitted
    FormValue<Date> startDate = new DateExtractor(startDateField).withMessage(invalidStartDateFormat)
        .extractValue()
        .validateWith(greaterThatOrEqual(today()).withMessage(startDateInThePast));

    FormValue<Date> endDate = new DateExtractor(endDateField).withMessage(invalidEndDateFormat)
        .extractValue()
        .validateWith(greaterThatOrEqual(today()).withMessage(endDateInThePast));
        .validateWith(greaterThatOrEqual(startDate).withMessage(startDateAfterEndDate));

    // Do something with form values and validation errors
}

private <T extends Comparable<T>> Validator<T> greaterThatOrEqual(T value) {
    return new GreaterThatOrEqualValidator<T>(value);
}

private <T extends Comparable<T>> Validator<T> greaterThatOrEqual(FormValue<T> value) {
    if (value.hasValue()) {
        return new GreaterThatOrEqualValidator<T>(value.value());
    }

    return new NoOpValidator<T>();
}
public class NoOpValidator<T> implements Validator<T> {
    private String message;

    @Override
    public Validator<T> withMessage(String message) {
        this.message = message;
        return this;
    }

    public FormValue<T> validate(T value) {
        return FormValue.some(value);
    }
}

Is it really a monad?

If a type wants to be a monad, it has to have:

  • unit operation that “wraps” a value with monad. It can be a constructor or a factory method. In our case FormValue.some represents the unit operation
  • bind operation transforming the monad into a next monad, exposing its internal value for a transformation function. FormValue.validateWith does this. Because Java doesn’t have first-class functions, we represent the validateWith operation argument as a method object – Validator

Furthermore, a monad must follow three monadic laws:

  1. identity – transforming to unit doesn’t change a monad
  2. m.bind { x -> unit(x) } ≡ m

    Previously mentioned NoOpValidator implements such a function:

    public FormValue<T> validate(T value) {
        return FormValue.some(value);
    }
    

    In case of Some, calling validateWith (bind method) with this Validator will return a new Some monad holding the same value. None‘s implementation returns always the same monad instance. Hence the first law is fulfilled.

  3. unit – unit must preserve the value inside the monad
  4. unit(x).bind(f) ≡ f(x)

    unit(x) corresponds to FormValue.some(x). Result of the execution of Some.validateWith is equivalent to the execution of the provided Validator:

    public FormValue<T> validateWith(Validator<T> validator) {
        return validator.validate(value);
    }
    
  5. associativity – order of monad composition doesn’t matter
  6. m.bind(f).bind(g) ≡ m.bind{ x -> f(x).bind(g) }

    Since None‘s validateWith returns always none (ignoring the bind function), it satisfies the associativity law.
    For Some it’s not so obvious. Let’s expand the left part of the theorem:

    some.validateWith(validator1).validateWith(validator2) => validator1.validate(value).validateWith(validator2)
    

    In order to implement the function in Java from the right side of the 3rd monadid law, we create an anonymous Validator:

    some.validateWith(
        new Validator<T>() {
            public FormValue<SSN> validate(SSN value) {
                validator1.validate(value).validateWith(validator2)
            }
        }
    );
    

    As you can see the result of the validation in the anonymous class is the same as of the expression expanded above.

    Conclusions

    Monads look abstract, esoteric, and, I admit, a little scary. Although from the functional programming domain, they can be implemented in imperative languages. They solve real-life problems (converstion and validation) in an elegant manner (we chained converters and validators with few ifs and no null checking).