Music, Computers and Deconstruction

Misc

On this page you will find some very small and simple examples of programs or libraries I have done. Most of the stuff on here is either entertaining (like the selfapp examples), or usefull, so I'd like to share it with the world. If you like to use anything found on this page, just go ahead. I might also expand the files found here to contain more functionality, fix bugs etc. If they grow beyond the state of small little gimmicks I might just decide to give them their own section. So just have a look to the right if you can't find things that were here a while ago.

Trie

This is a basic Trie structure in OCaml that supports approximate matching on tries. You can use it to store any kind of data by any kind of sequenced index. One way I use it is to store strings, so I can find strings that are similar very fast. This can be used for efficient spell checkers. However since it is functorized and not limited to character indexes you can use anything you like. Right now only the distance using the Levensthein Metric is supported, but I might decide to add other distance measures as well. It could easily be changed to us generalized Levensthein or DTW as well.

As you know all common prefixes of the sequences are stored only once, so any algorithm on the trie is reasonably fast if many of the sequences share a lot. If less is shared it gets a lot slower.

The algorithm for approximate matching is described in this paper. When I found this I was really surprised this is not more common.

The way to use this is to provide two functions that tell the Trie how to derive sequences and values from raw data you want to store. You can then add elements to the Trie from raw data, query if some data is contained and do some approximate matching. All data Structures are fully pervasive. The only drawback is that you need full data for querying, which is good when the indexed and the key data are the same (see at implemented StringTrie, why this makes sense sometimes). This has to do mainly with the way I use the trie, but might not fit the way you want to use it. For this you can either provide some meaningless values in your data, which wont be used in querying. Or you can change the code in about five places to take index lists on querying.

Simple OCaml trie

2142bytes tar.gz

Self-Application

In our course on compiler construction our teacher told us of the concept of self application. What this means in general is that you write a recursive function without any real use of recursion. This is incredibly useful for understanding continuations and other advanced topics in programming languages. Also self application is one of the basics for recursion in lambda calculus, which does not even have any direct notion of recursion. Here is for example how to handle a factorial function:

The definition of factorial is usually like this

Graph

Normally you would use recursion provided by the programming language to write this function. In lambda calculus you have to use some tricks to do this. The main trick consists in providing another argument that specifies the function to call on the recursive step. For this function you then pass the function itself, like this (informal lambda calculus)

Graph

To use this function you could either provide it with itself as a parameter, like this

Graph

or use fixed-point combinators that would calculate the real recursive function from this one (note: the combinator used below is not a real fixed point combinator, nor is one used, since the recursive call used f twice again. If you want to drop the second use of f inside the function an actuall y combinator is needed):

Graph

When our teacher introduced this concept he gave almost exactly the examples above as well as some Haskell examples. Since I didn't like Haskell I just decided to play around with this idea in a few languages, so I did this in a couple of more languages. Have fun with these examples.

Some examples for self application

2142bytes tar.gz