henkerik.github.io/css.html at master · henkerik/henkerik.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# CSS Evaluator

In this post I will explain how to write a monadic CSS selector evaluator. The CSS specification defines selectors, which indicate to which DOM elements a given list of style declarations needs to be applied. For example, the selector:

#test > li

selects the two li elements in the following document:

<body id="body">
  <p>P1</p>
  <ul id="test">
    <li>A</li>
    <li>B</li>
   </ul>
   <p>P2</p>
</body>

How do we write a function which takes as an input a CSS selector and returns a list of the selected DOM elements? Let's start by writing a function which selects the child elements of a given element based on a predicate function. I will give an implementation Javascript, but I will write a type signature for each function using Scala notation.

// selectByPredicate: (Element => Bool) => Element => List[Element]
function selectByPredicate (f) {
  return function (e) {
    var result = new Array();
    for (var i = 0; i < e.children.length; i++)
      if (f(e.children[i])) result.push(e.children[i]);
    return result;
  }
}

By using this general select function we are able to write specialized select functions. We may for example write a function which selects child elements which have a specific id or a specific tagname:

// selectById: String => Element => List[Element]
function selectById (id) {
  return selectByPredicate(function (e) { return e.id == id; });
}

// selectByTagName: String => Element => List[Element]
function selectByTagName (name) {
  return selectByPredicate(function (e) { return e.tagName == name.toUpperCase(); });
}

Now, we are able to translate the individual parts of the CSS selector to
a function by partially applying our select functions:

CSS Selector Part  Partial Applied Selector Function  Remaining Type
#test              selectById('test')                 Element => List[Element]
li                 selectByTagName('li')              Element => List[Element]

Our next job is finding a method to chain these partially applied selector functions together. Notice how the remaining type of our partially applied functions line up. However, one quickly sees that simply using function composition is not going to work here: the result of a select function is a list of element while the input of a select function is just a single element.

This looks remarkabily similar to the problem we faced while composing functions which returned an Option. Today, we apply the same trick. In Javascript we may implement flatMap on lists as following:

// flatMap[A,B]: List[A] => (A => List[B]) => List[B]
Array.prototype.flatMap = function (f) {
  return this.map(f).flatten();
}

// flatten[A]: List[List[A]] => List[A]
Array.prototype.flatten = function () {
  return this.reduce(function (left, right) {
    return left.concat(right)
  }, new Array());
}

Now, we are able to compose the individual select function together and write one function which selects the elements given by the CSS selector #test > li:

// xs contains the result of the CSS selector: #test > li
var body = document.getElementById('body');
var xs = [body].flatMap(selectById('test')).flatMap(selectByTagName('li'))

This may still look a bit difficult to understand, but imagine if Javascript supported for-comphrensions. In that case we would have been able to write:

// xs contains the result of the CSS selector: #test > li
var body = document.getElementById('body');
var xs = for {
  e1 <- selectById ('test')(body)
  e2 <- selectByTagName ('li')(e1)
} yield e2

Looks quite elegant right? For those interested, a working example is available here.