…and in JavaScript, using Sweet.js

This post is a continuation of my previous post, Capturing abstractions in Lisp.

Today I was playing with Sweet.JS, a JavaScript library that adds the possibility to make macros within the language.

I went through the tutorial and it is pretty straight-forward.

// delay needs to be a macro in order for the code to work correctly.
// Otherwise the invocation of delay will evaluate all its arguments eagerly.
syntax delay = function (ctx) {
    let x = ctx.next().value;
    return #`(function() { return ${x} })`;
}

// similarly for cons-stream
syntax cons_stream = function(ctx) {
    const [...args] = ctx.next().value.inner();

    let param1 = args[0];
    let param2 = args.slice(2);

    return #`([${param1}].concat(delay(${param2})))`;
}

// force just evaluates
function force(x) {
    return x();
}

function next_integer(x) {
    return cons_stream(x, next_integer(x+1));
}

function all_positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    if (j == 0) {
        return list[0];
    } else {
        return integer_ref(force(list[1]), j - 1);
    }
}

var integers = all_positive_integers();
// display 100th number:
console.log(integer_ref(integers, 100));

With this code snippet, we can see that using this library we get a very powerful Lisp-like syntax 🙂

Capturing abstractions in Lisp

I was skimming through SICP (after a pause) and I came across the chapter where Streams are discussed.

For those that have experience with JS Promises, Streams can be thought of as Promises. They allow us to make an illusion of infinity, e.g. all positive integers, by deferring evaluation.

For example, to generate all positive integers, we make a pair (1, next_int(1)), and then to evaluate the second member of that pair is (2, next_int(2)) and so on, for the nth number producing a list (1, (2, (…, (n, next_int(n))))) which will do n evaluations.

Here’s an implementation in Scheme that defines cons-stream (which will allow us to produce promises) and uses that to generate all integers infinitely (but not really, since all it does is just defer evaluation).

; delay needs to be a macro in order for the code to work correctly.
; Otherwise the invocation of delay will evaluate all its arguments eagerly.
(define-syntax delay
  (syntax-rules ()
    ((delay a)
     (lambda () a))))
; (defmacro delay (a) `(lambda () ,a))

; similarly for cons-stream
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
      (cons a (delay b)))))
; (defmacro cons-stream (a b) `(cons ,a (delay ,b)))

; force just evaluates
(define (force a) (a))

(define (next-integer x) (cons-stream x (next-integer (+ x 1))))

(define all-positive-integers (next-integer 0))

(define (integer-ref list i)
  (cond ((= i 0) (car list))
    (else (integer-ref (force (cdr list)) (- i 1)))))

; display 100th number:
(integer-ref all-positive-integers 100)

Looks and works pretty good!

Now, we can try doing the same in JS:

function force(x) {
    return x();
}
function cons_stream(a) {
    return function(b, c) {
        // this is delay basically but we can't abstract it in another method
        // since it will evaluate the params, so we need to use scope
        return function() {
            return [a].concat(b(c));
        }
    }
}

function next_integer(x) {
    return cons_stream(x)(next_integer, x+1);
}

function positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    var item;

    // evaluate initially
    list = force(list);

    while (j != 0) {
        // get the last item from the list (promise)
        item = list.pop();

        // append it in its evaluated form
        list = list.concat(force(item));

        j--;
    }

    // exclude last item since it's a new promise
    return list[list.length - 2];
}

var all_positive_integers = positive_integers();

// display 100th number:
console.log(integer_ref(all_positive_integers, 100));

The code is a bit longer, but it works equally good.

In JS we can achieve the same effect that the Lisp macro does by using scopes.

But in my opinion, Lisp’s syntax is more powerful with the ability to not evaluate parameters because it allows us to capture abstractions such as delay, whereas in JS we couldn’t do the same.

JavaScript Patterns overview

Chapter 1

Discusses the following types of patterns:

– Design patterns: singleton, factory, decorator
– Coding patterns: js related
– Antipatterns

Maintainable code is one that:

– Is readable
– Is consistent
– Is predictable
– Looks as if it was written by the same person
– Is documented

One of the general rules in the Gang of Four book says, “Prefer object composition to class inheritance.”. This means that if you can create objects out of available pieces you have lying around, this is a much better approach than creating long parent-child inheritance chains and classifications. In JavaScript it’s easy to follow this advice-simply because there are no classes and object composition is what you do anyway.

Antipattern: do not use. right-to-left evaluation

function foo() {
var a = b = 0;
// ...
}

Antipattern: implied global

function sum(x, y) {
result = x + y;  // The rule of thumb is to always declare variables using var
return result;
}

Antipattern: the first alert will say “undefined” because myname is considered declared as a local variable to the function.

myname = "global"; // global variable
function func() {
alert(myname); // "undefined"
var myname = "local";
alert(myname); // "local"
} func();

Antipattern: don’t augment prototypes because Object.prototype.hasOwnProperty doesn’t show prototype defs, only own

if (typeof Object.protoype.myMethod !== "function") {
Object.protoype.myMethod = function () {
// implementation...
};
}

In the following example, eval() can access and modify a variable in its outer scope, whereas Function cannot (also note that using Function or new Function is identical):

(function () {
var local = 1;
eval("local = 3; console.log(local)"); // logs 3
console.log(local); // logs 3 }());
(function () {
var local = 1;
Function("console.log(typeof local);")(); // logs undefined }());

warning: unexpected return value. need return and { to be on the same line. This behavior can cause troubles when a function returns an object literal and the opening brace is on the next line:

function func() {
return
{
name: "Batman"
};
}

For your constructors, you can use upper camel case, as in MyConstructor(), and for function and method names, you can use lower camel case, as in myFunction(), calculateArea() and getFirstName(). And what about variables that are not functions? Developers commonly use lower camel case for variable names, but another good idea is to use all lowercase words delimited by an underscore: for example, first_name, favorite_bands, and old_company_name.

Chapter 2

Don’t use new Object(); – use the simpler and reliable object literal instead (var x = { ... }).

When you invoke the constructor function with new, the following happens inside the function:

1. An empty object is created and referenced by this variable, inheriting the prototype of the function.
2. Properties and methods are added to the object referenced by this.
3. The newly created object referenced by this is returned at the end implicitly (if no other object was returned explicitly).

var Person = function (name) {
// create a new object
// using the object literal
// var this = {}; i.e. Object.create(Person.prototype);

// add properties and methods this.name = name;
this.say = function () {
return "I am " + this.name; };
// return this;
};

var Objectmaker = function () {
// this `name` property will be ignored
// because the constructor
// decides to return another object instead this.name = "This is it";
// creating and returning a new object
var that = {};
that.name = "And that's that";
return that;
};
// test
var o = new Objectmaker();
console.log(o.name); // "And that's that"

As can you see, you have the freedom to return any object in your constructors, as long as it’s an object. Attempting to return something that’s not an object (like a string or a boolean false, for example) will not cause an error but will simply be ignored, and the object referenced by this will be returned instead.

Chapter 3

> var a = function() { }
undefined
> a.name
''
> var a = function a() { }
undefined
> a.name
'a'
>

Chapter 4

Dependencies, this has faster resolution

var event = YAHOO.util.Event, dom = YAHOO.util.Dom;

The solution to this unexpected behavior is to be careful not to pass references to objects and arrays you want to keep private. One way to achieve this is to have getSpecs() return a new object containing only some of the data that could be interesting to the consumer of the object. This is also known as Principle of Least Authority (POLA), which states that you should never give more than needed. In this case, if the consumer of Gadget is interested whether the gadget fits a certain box, it needs only the dimensions. So instead of giving out everything, you can create getDimensions(), which returns a new object containing only width and height. You may not need to implement getSpecs() at all.

Another approach, when you need to pass all the data, is to create a copy of the specs object, using a general-purpose object-cloning function. The next chapter offers two such functions-one is called extend() and does a shallow copy of the given object (copies only the top-level parameters). The other one is called extendDeep(), which does a deep copy, recursively copying all properties and their nested properties.

var myobj = (function () { // private members
var name = "my, oh my";
// implement the public part return {
getName: function () {
return name; }
}; }());
myobj.getName(); // "my, oh my"

This example is also the bare bones of what is known as “module pattern,” which we examine in just a bit.

One drawback of the private members when used with constructors is that they are recreated every time the constructor is invoked to create a new object. This is actually a problem with any members you add to this inside of constructors. To avoid the duplication of effort and save memory, you can add common properties and methods to the prototype property of the constructor. This way the common parts are shared among all the instances created with the same constructor.

Gadget.prototype = (function () { // private member
var browser = "Mobile Webkit"; // public prototype members return {
getBrowser: function () {
return browser; }
}; }());

The module pattern is a combination of several patterns described so far in the book, namely:

– Namespaces
– Immediate functions
– Private and privileged members
– Declaring dependencies

var x = function(arg) {
if (!(this instanceof x)) {
console.log('Not a singleton, using constructor `' + arg + '`');
return new x(arg);
}
this.moo = arg;
}
var myobj1 = new x('using new');
var myobj2 = x('without new');
console.log(myobj1);
console.log(myobj2);

// constructor
var Gadget = function () {};
// a static method
Gadget.isShiny = function () { return "you bet"; };
// a normal method added to the prototype
Gadget.prototype.setPrice = function (price) { this.price = price; };
The static isShiny() is invoked directly on the constructor, whereas the regular method needs an instance:
// calling a static method
Gadget.isShiny(); // "you bet"
// creating an instance and calling a method
var iphone = new Gadget(); iphone.setPrice(500);

Sometimes it could be convenient to have the static methods working with an instance too. This is easy to achieve by simply adding a new method to the prototype, which serves as a facade pointing to the original static method:

Gadget.prototype.isShiny = Gadget.isShiny;
iphone.isShiny(); // "you bet"

In such cases you need to be careful if you use this inside the static method. When you do Gadget.isShiny() then this inside isShiny() will refer to the Gadget constructor function. If you do iphone.isShiny() then this will point to iphone.

var Gadget = (function () {
// static variable/property
var counter = 0;
// returning the new implementation // of the constructor
return function () { console.log(counter += 1); };
}()); // execute immediately

Chapter 5

Classical Pattern #1-The Default Pattern (prototype chain inheritance)

function inherit(C, P) {
C.prototype = new P();
}
var x = function() {}
var y = function() {}
y.prototype.a = b;
inherit(x, y);

lookup: x -> y -> y.prototype. Object #3 doesn’t have such a method, so it looks up to #2 via the prototype chain. Object #2 doesn’t have it either, so it follows the chain up to #1, which does happen to have it. One drawback of this pattern is that you inherit both own properties added to this and prototype properties. Most of the time you don’t want the own properties, because they are likely to be specific to one instance and not reusable.

Classical Pattern #2-Rent-a-Constructor

function Child(a, c, b, d) {
Parent.apply(this, arguments);
}

This way you can only inherit properties added to this inside the parent constructor. You don’t inherit members that were added to the prototype. But nothing from the prototype gets inherited.

Classical Pattern #3-Rent and Set Prototype

function Child(a, c, b, d) {
Parent.apply(this, arguments);
}
Child.prototype = new Parent();

A drawback is that the parent constructor is called twice, so it could be inefficient. At the end, the own properties (such as name in our case) get inherited twice.

Classical Pattern #4-Share the Prototype

Unlike the previous classical inheritance pattern, which required two calls to the parent constructor, the next pattern doesn’t involve calling the parent constructor at all. The rule of thumb was that reusable members should go to the prototype and not this. Therefore for inheritance purposes, anything worth inheriting should be in the prototype. So you can just set the child’s prototype to be the same as the parent’s prototype:

function inherit(C, P) {
C.prototype = P.prototype;
}

However if one child or grandchild somewhere down the inheritance chain modifies the prototype, it affects all parents and grandparents.

Classical Pattern #5-A Temporary Constructor

The next pattern solves the same-prototype problem by breaking the direct link between parent’s and child’s prototype while at the same time benefiting from the prototype chain. This pattern has a behaviour slightly different from the default pattern (classical pattern #1) because here the child only inherits properties of the prototype.

function inherit(C, P) {
var F = function () {};
F.prototype = P.prototype;
C.prototype = new F();
C.uber = P.prototype; // Store the super class
C.prototype.constructor = C; // If you don't reset the pointer to the constructor, then all children objects will report that Parent() was their constructor
}

A common optimization of the Holy Grail pattern is to avoid creating the temporary (proxy) constructor every time you need inheritance.

var inherit = (function () {
var F = function () {};
return function (C, P) {
F.prototype = P.prototype;
C.prototype = new F();
C.uber = P.prototype;
C.prototype.constructor = C;
}
}());

function f() {
var args = [].slice.call(arguments, 1, 3);
return args;
}
// example
f(1, 2, 3, 4, 5, 6); // returns [2,3]

function bind(o, m) {
return function () {
return m.apply(o, [].slice.call(arguments));
};
}

Chapter 6

function Universe() {
// do we have an existing instance?
if (typeof Universe.instance === "object") {
return Universe.instance;
}
// proceed as normal
this.start_time = 0; this.bang = "Big";
// cache
Universe.instance = this;
// implicit return:
return this;
}

Another way to do the class-like singleton is to use a closure to protect the single instance. You can implement this by using the private static member pattern discussed in Chapter 5. The secret sauce here is to rewrite the constructor:

function Universe() {
// the cached instance
var instance = this;
// proceed as normal
this.start_time = 0; this.bang = "Big";
// rewrite the constructor
Universe = function () {
return instance;
};
}

Patterns

Singleton

Creating only one object of a “class.” We looked at several approaches if you want to substitute the idea of a class with a constructor function and preserve the Java-like syntax. Otherwise, technically all objects in JavaScript are singletons. And also sometimes developers would say “singleton,” meaning objects created with the module pattern.

Factory

A method that creates objects of type specified as a string at runtime.

Iterator

Providing an API to loop over and navigate around a complex custom data structure.

Decorator

Tweaking objects at runtime by adding functionality from predefined decorator objects.

Strategy

Keeping the same interface while selecting the best strategy to handle the specific task (context).

Facade

Providing a more convenient API by wrapping common (or poorly designed) methods into a new one.

Proxy

Wrapping an object to control the access to it, with the goal of avoiding expensive operations by either grouping them together or performing them only when really necessary.

Mediator

Promoting loose coupling by having your objects not “talk” to each other directly but only though a mediator object.

Observer

Loose coupling by creating “observable” objects that notify all their observers when an interesting event occurs (also called subscriber/publisher or “custom events”).

The difference between code and data

Today I finished watching SICP 2B video and it was what inspired me to write this post.

Recently I started working on SICP (https://github.com/bor0/sicp) and I also implemented tinylisp (similar to Peter Norvig’s lis.py) in PHP (https://github.com/bor0/tinylisp).

So the 2B video ends with Abelson defining cons in terms of procedures that return other procedures. In this way, one can ask the question “What really is data?”

In almost all of the widely used languages today (JavaScript, PHP, Python), you’ll find that functions are all first-class objects, and this is all thanks to Lisp.

The contract for cons, car, and cdr is as follows:

(car (cons x y)) = x
(cdr (cons x y)) = y 

And that’s all really is to data. Any kind of data can be constructed using cons, car, and cdr.
So here is how we can implement cons, car, and cdr in Lisp:

(define (cons a b)
(lambda (pick)
(if (= pick 1) a b)))

(define (car a) (a 1))
(define (cdr a) (a 2))

And then ask the evaluator:

> (cons 1 2)
#
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2
>

One needs to take a moment here and think how these are implemented (and possibly try to reduce the examples using the substitution model to get a sense of what really is going on).

For the funs, I implemented this in PHP:

<?php
function cons($x, $y) {
// context 1
return function ($a) use ($x, $y) {
// context 2
return ($a == 1) ? $x : $y;
};
}

function car($x) {
return $x(1);
}

function cdr($x) {
return $x(2);
}

$x = cons(1, 2);
var_dump($x(1));
var_dump(car($x));
var_dump(cdr($x));
boro@bor0:~$ php test.php
int(1)
int(1)
int(2)
boro@bor0:~$

This can give you an idea of how powerful it is to have multiple contexts, and the things we can do given them.

If you look at the tinylisp code, you’ll get a sense of how cons works in terms of contexts.

Svpion Fifth problem

I attempted myself to solve #5 from Five programming problems every Software Engineer should be able to solve in less than 1 hour in Haskell.

So the task is:
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Initially I thought,
“Hey, this should be easy. All we need to do is create an algebra that contains Addition, Subtraction, and Multiplication (being concatenation) and we should be good!”

So I proceeded:

data Expr =
A Expr Expr |
S Expr Expr |
C Expr Expr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (C a b) = parse a * 10 + parse b
parse (I a) = a

This should be it! So for example 1 + 2 + 3 would be A (I 1) (A (I 2) (I 3)), and getting the result of it is to call parse like:

*Main> parse $ A (I 1) (A (I 2) (I 3))
6

Now all we need to do is create all possibilities of the form (1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9) and replace _ with any of the three operators and then finally do something like filter (== 100) parse x.

But using this grammar, there are some non-valid cases such as C (A (I 1) (I 2)) (I 3).
These are cases that we must exclude, for if we don’t, then what this expression would evaluate to is 33, i.e. (1 + 2) * 10 + 3, but this is not a valid expression given the stated task.
However 1 + 23 or 12 + 3 or 1 + 2 + 3 are.

To take care of this, we will slightly rework our grammar and parsing functions:

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

Another constraint that we need to add is that the concatenations need to be successive. So we somehow need to exclude those cases as well from all of the possibilities. Let’s call this function getCExprs. So what getCExprs should do is, given a list, it should return possible successive concatenations of that list. Successive concatenations is what will allow us to remove the non-valid cases.

E.g. getCExprs [I 1,I 2,I 3] = [I 1,C (I 1) (I 2),C (C (I 1) (I 2)) (I 3)].

Additionally (we’ll see why within the foldingFunction), we want getCExprs to return the remaining part of the list (digits) it’s working on, so:

getCExprs [I 1,I 2,I 3] = [([I 2,I 3],I 1),([I 3],C (I 1) (I 2)),([],C (C (I 1) (I 2)) (I 3))].

To implement this, we’ll need a help function called listToC that given a list [I 1,I 2,I 3], it will turn it into its concatenated algebraic version, C (C (I 1) (I 2)) (I 3).

The definition for this is trivial:

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

Now we are ready to go for getCExprs:

getCExprs :: [CExpr] -> [([CExpr], CExpr)]
getCExprs x = go 1 (tail $ inits x)
where
go n xs@(x':xs') = (drop n x, listToC x') : go (n + 1) xs'
go _ [] = []
Some simple tests:

*Main> getCExprs $ map I [1,2,3]
[([I 2,I 3],I 1),([I 3],C (I 1) (I 2)),([],C (C (I 1) (I 2)) (I 3))]
*Main> getCExprs $ map I [1..9]
[([I 2,I 3,I 4,I 5,I 6,I 7,I 8,I 9],I 1),([I 3,I 4,I 5,I 6,I 7,I 8,I 9],C (I 1) (I 2)),([I 4,I 5,I 6,I 7,I 8,I 9],C (C (I 1) (I 2)) (I 3)),([I 5,I 6,I 7,I 8,I 9],C (C (C (I 1) (I 2)) (I 3)) (I 4)),([I 6,I 7,I 8,I 9],C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)),([I 7,I 8,I 9],C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)),([I 8,I 9],C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)),([I 9],C (C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)) (I 8)),([],C (C (C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)) (I 8)) (I 9))]
*Main>

Seems to be working fine!

Next, we want to create a function f that has three parameters:
1. Current expression calculated with add/sub so far, Expr
2. Current operation being done, String
3. Remaining list of expressions (digits and successive concatenated digits) to work on, [CExpr]
and this function should return a list of (Expr, String), i.e. which expression is produced for what operations.

So we have:

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]

This should be a fold, so what f should do is basically go through all valid possibilities (which are created by getCExprs), so, what we have so far:

f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs

In the first definition of f, we pattern match against an empty list, which is basically the base case and it returns the last pair of (sum, operations) done at that point.

So, this is what we currently have:

import Data.List (inits, nub)

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

getCExprs :: [CExpr] -> [([CExpr], CExpr)]
getCExprs x = go 1 (tail $ inits x)
where
go n xs@(x':xs') = (drop n x, listToC x') : go (n + 1) xs'
go _ [] = []

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]
f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs
where
foldingFunction = undefined

So, all we need to do is implement foldingFunction and we are done.

To be able to implement foldingFunction, we need to look at getCExprs and see what it produces for us. We know that it gives us back a pair, ([CExpr], CExpr). CExpr is the current concatenations done, and [CExpr] is the remaining part of the list.

Therefore,
foldingFunction (a, b) l = undefined

Remember f had three params. The way we defined f makes it easily callable by the foldingFunction.

We need to call f from within the foldingFunction and add the current value we are iterating to the sum. We also need to note which operation we are applying, and to pass the current list of digits we are working on. Note that we have the variable s (expression calculated so far) in the scope since we will define foldingFunction within f itself. We also have the variable b produced by getCExprs, but its type is CExpr. if b :: CExpr, then CE b will be Expr, which is what our function f requires, i.e. to parse a complete expression (Expr), and not just digits or concatenated digits (CExpr).

So:
foldingFunction (a, b) l = f (A s (CE b)) (“+” : ops) a

In this case, we are calling f while adding s and b, i.e., we add b to the current expression so far, and then we pass the remaining list of numbers (a) to f.

This takes care of the addition. To make messages more verbose, we’ll implement a function called “calculated” which in details will explain what’s going on:

foldingFunction (a, b) l = f (A s (CE b)) (calculated “+” b) (drop a xs)
calculated op b = (op ++ show (parseCE b)) : ops

Similarly, we need to do the same for the operation minus. And then we need to append all of the results in a single list:
foldingFunction (a, b) l =
f (A s (CE b)) (calculated “+” b) a
++
f (S s (CE b)) (calculated “-” b) a
++ l

So the full code is:

import Data.List (nub)

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

getCExprs xs = map (\x -> (drop x xs, listToC (take x xs))) [1..length xs]

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]
f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs
where
foldingFunction (a, b) l = f (A s (CE b)) (calculated "+" b) a
++ f (S s (CE b)) (calculated "-" b) a
++ l
calculated op b = (op ++ show (parseCE b)) : ops

main = do
let l = f (CE (I 0)) [] (map I [1..9])
let l' = filter (\x -> parse (fst x) == 100) l
mapM_ (\(x, y) -> print $ concat $ reverse y) l'

Call main to get:

[1 of 1] Compiling Main             ( test.hs, interpreted )
iOk, modules loaded: Main.
*Main> main
"+1+2+3-4+5+6+78+9"
"+1+2+34-5+67-8+9"
"+1+23-4+5+6+78-9"
"+1+23-4+56+7+8+9"
"-1+2-3+4+5+6+78+9"
"+12+3+4+5-6-7+89"
"+12+3-4+5+67+8+9"
"+12-3-4+5-6+7+89"
"+123+4-5+67-89"
"+123-4-5-6-7+8-9"
"+123+45-67+8-9"
"+123-45-67+89"
*Main>

Solving this problem in a functional language like Haskell reveals its background when it’s represented using an algebraic data type. For instance, if this problem was solved in Python, you would run through all combinations of “1_2_3_4_5_6_7_8_9”, change underscores with plus, minus, or append, and then eval the string expression. But if you solve it this way, you wouldn’t have any deeper insight regarding its algebra, e.g. the “successive concatenations” part might not be immediately visible.

Algebraic data types representation helps us with adding constraints, but to some point. Additional more complex constraints were handled by the functions themselves.

This is why I do not believe this is solvable in under 1 hour when you first meet this problem. There is much more background in this than what the author states.