Thu 12 April 2018

Filed under Programming languages

Tags ocaml purely functional

Implementation of sets using nothing but functions would be one of the first tricks in the “100 Fun Things to Do With Functions and Closures” book if that book existed. It may not be very practical, but it may help people get into the functional mindset. We'll use OCaml for demonstration.

Our implementation will support the following operations:

  • Checking if a value belongs to a set
  • Inserting new elements into existing sets
  • Creating unions and complements of sets

We'll represent a set S as a function s x such that s x = true if x is a member of S and false otherwise. This way the first goal of our project is already met.

The type of the set functions will be 'a -> bool (if you are new to ML, the 'a here is a type variable that can be replaced by any type, as long as all occurences of 'a within an expression are replaced with the same type — this is known as parametric polymorphism).

In this approach, a set and a function that checks if a value belongs to it is the same, but we can add a little syntactic sugar to make it look as if sets were somehow special:

let is_in s x = s x

The empty set can be represented as a function that returns false for any argument, since by definition it's a set that has no elements, and nothing belongs to it:

let empty x = false

How can we represent a non-empty set? Let's start with a set of just one element. To find out if something belongs to it, we just need to compare it with a fixed value, and return false if they are not equal:

let set_of_one x =
  if x = 1 then true
  else false

Or we can rewrite it using the empty function we've defined earlier as the base case for recursion:

let set_of_one x =
  if x = 1 then true
  else empty x

Note that we've just essentially created a non-empty set from the empty set. Now we have the template for set functions, and it's easy to see how to make a set of two elements (say 1 and 2) from set_of_one:

let set_of_one_and_two x =
  if x = 2 then true
  else set_of_one x

Now we are just one step away from the second goal of creating a function for inserting elements into existing sets. All we need is a simple higher order function that takes a set s and value e and returns a new function s' x that returns true is x = e, or the value of s x otherwise.

let insert e s =
  fun x -> if x = e then true else s x

We can build sets of any finite size from the empty set with it:

let one = insert 1 empty
let two = insert 2 one
let three = insert 3 two

let a = in_set three 2 (* true *)
let b = in_set three 4 (* false *)

Now to the union and the complement. You might have noticed that with our insert function, we'are essentially representing finite sets as unions of single element sets, but here we are talking about a user-friendly way to create a union of two arbitrary sets.

By definition, an element is in the union of sets A and B if it belongs to at least one of them. We can implement the union function simply by following the definition.

let union s s' =
  fun x -> (is_in s x) || (is_in s' x)

The definition of the (relative) complement of sets A and B is a set that includes all elements of A that are not in B.

let complement s s' =
  fun x -> (is_in s x) && not (is_in s' x)

Let's test them:

let s = insert 3 empty |> insert 2
let s' = insert 1 empty

let u = union s s'
let c = complement u s'

let x = is_in u 3 (* true *)
let y = is_in u 1 (* true *)
let z = is_in u 0 (* false *)

let v = is_in c 1 (* false *)
let w = is_in c 3 (* true *)

Now that all goals are met, we can even wrap everything into a module:

module type MYSET = sig
  type 'a set = 'a -> bool
  val empty : 'a set
  val is_in : 'a set -> 'a -> bool
  val insert : 'a -> 'a set -> 'a set

  val union : 'a set -> 'a set -> 'a set
  val complement : 'a set -> 'a set -> 'a set
end

module MySet : MYSET = struct
  type 'a set = 'a -> bool

  let empty x = false

  let is_in s x = s x

  let insert e s =
    fun x -> if x = e then true else s x

  let union s s' =
    fun x -> (is_in s x) || (is_in s' x)

  let complement s s' =
    fun x -> (is_in s x) && not (is_in s' x)
end
Comment

Sat 07 April 2018

Filed under Development

Tags x86-64 linux assembly tutorial

I've stumbled upon two posts where Jessica McKellar demonstrates how to make a C program on Linux without using libc. They were written in 2010 when 32-bit x86 was far from extinct though, and use the old 32-bit ABI — a problem most examples of low level programming on UNIX-like systems …

Read More

Mon 02 April 2018

Filed under Development

Tags python setuptools

Package data installation sometimes requires balance between ease of writing installation procecures for it and ease of accessing that data. That's especially apparent when someone who is not a developer wants to be able to edit that data in place. Editing it in place is a bad practice of course …

Read More

Sat 31 March 2018

Filed under Networking

Tags cisco

From the fact that I'm a VyOS maintainer, you can guess that I'm not a fan of Cisco routers, but I'm a big fan of Cisco Catalyst switches. They have never failed me yet, and among all L2 switches they have the least annoying CLI, even though it does have …

Read More

Wed 14 March 2018

Filed under Development

Tags mtu tunnel web

A new version of encapcalc the MTU/MSS calculator is now live at https://baturin.org/tools/encapcalc.

What's new?

  • Updated, more mobile device friendly UI
  • Calculating frame size from payload in addition to calculating PDU from parent MTU
  • Support for ESP and AH with 96-bit HMAC (contributed by Zmegolaz …
Read More

Fri 09 March 2018

Filed under System administration

My current VPS is running CentOS 6, and, frankly, it long started showing its age. Not very surprising if we remember that it was released in 2011. Even with all efforts from EPEL, Remi, and Software Collections maintainers, running new applications on new OS versions is obviously easier than on …

Read More

Wed 28 February 2018

Filed under Networking

Tags routing anycast bgp

It is well known that due to limited practical size of a UDP packet that can be transmitted without fragmentation, the number of DNS root servers is limited to 13 addresses. There are indeed 13 root servers named from A to M (a.root-servers.net, b.root-servers.net and so …

Read More

Wed 21 February 2018

Filed under Programming languages

Tags duck typing python ocaml

So called “duck typing” is often poorly explained and thus often misunderstood. Its name and the adage associated with it (“if it walks like a duck and quacks like a duck, then it is a duck”) don't do it any favors either.

I've always found that analogy strange and misleading …

Read More

Tue 20 February 2018

Filed under Misc

Looks like my blogging cycle is two years in and two years out. Not that I run out of things to write about, it's just that good technical writing is a surprisingly time consuming endeavor. You get to verify every example, check every proof, look up every detail in the …

Read More

dmbaturin's blog © Daniil Baturin Powered by Pelican and Twitter Bootstrap. Icons by Font Awesome and Font Awesome More