Scala Lists, Eager and Lazy

So, I returned to looking at Scala. I wanted to implement two types of lists: a regular linked list and a lazy list (i.e., a list where you don’t evaluate the tail before you need it). Both are already available in Scala, but I’m solely doing this for educational purposes.

KMP Implementations

Following on my previous post I set out to implement the Knuth-Morris-Pratt algorithm.

This algorithm shifts the pattern p along x, exploiting the structure in p to skip positions we know cannot match. To do this, it uses a so-called border array that we need to pre-compute.

Simple String Search Implementations

I’ll get back to playing with Scala soon, but since I don’t know which skills to brush up on, I also decided to play with a few other things.

I have taught string algorithms for over a decade, so I figured that using a few simple algorithms I know very well would be an interesting way to play with how the same goal can be achieved in different languages.

Giving Scala a Go—Playing with Lists

Soon, I will be unemployed — the needs of Kvantify and my interests and qualifications have diverged over the last year — so it is time to brush up on my skills, so I look interesting for potential future employer. Since I don’t know what a future employer will be looking for, this mainly means finding something I’m not familiar with but interested in and playing with it. Today, the choice fell on Scala.

Prefix Doubling Attempts

I’ve been working on an algorithm for suffix array construction today. It’s called prefix doubling, but I don’t have a link, sorry. I think it comes from this paper but I don’t have access to it at home.

CPS and Iterators in C

Today, I want to talk about continuation-passing-style (CSP). This is a general approach you can use to translate recursions into tail-calls.

What’s tail-calls, I (imagine hearing) you ask?

A tail-call is when a function calls another function as the last thing it does. Tail-recursion is when that last call is a recursive call, but that is just a special case of tail-calls.

C Slices

About those slices I mentioned yesterday, here’s what’s that about.

I’m working on some string algorithms and more straightforward C implementations than those I put in my book.

I implemented all the algorithms and data structures I use in my string algorithm class in Python and Go in the spring,^[I’m toying with the idea of writing string algorithms books for those languages, but I have a long list of writing obligations, so I don’t know if that will ever happen.] and I plan to implement them in Rust as soon as I get the time. Still, I’m also playing with the idea of reimplementing everything in C in a (perhaps) more accessible form.

Macro Metaprogramming

I’ve been working on a small C library for Python- or Go-like slices the last couple of weeks. Essentially arrays, but where I can index from the end using negative numbers (like in Python) and where I can extract a sub-slice, x[i:j], in constant time (like in Go; I implement them the same way as Go does).

'Witness' arrays

The other day I was reminded of an exercises we got first or second year when I studied computer science. It is a cool little trick, that I’ve never seen outside of that exercise, so I thought I’d share it.