blog.poucet.org Rotating Header Image

April, 2008:

Lazy memoization

It seems the concept of an “infinite array” in my previous blog post prompted some interest. Two very good suggestions came from Chung-chieh Shan. As usual, his code was minimal but powerful.

  • Use an infinite list of exponentially growing arrays.
  • Use the following data-structure: data Tree a = Tree a (Tree a) (Tree a)

I have to admit that I am not fully clear yet on how to encode it in the above tree.  Conceptually it should be trivial to encode, for instance, [0..] to such a binary structure, after all it’s just bits.  However, momentarily it escapes me.

Another solution came up through a discussion on #haskell with dcoutts and sjanssen(Spencer Janssen). At first the idea was to deal with lazy arrays, but quickly the discussion turned to the concept of a generic caching policy, brought up by dcoutts. One can imagine a combinator library of caching policies. And then one would memoize a function as follows:

memo :: CachingPolicy -> (i -> e) -> (i :->: e)

With this structure, one would generate a memoized function that uses the caching policy to evict old entries. Obviously this would require the use of unsafePerformIO under the hood to mutate the data-structure. It would definitely be an interesting paper, according to dcoutts, all that is required is an application as a strong showcase.

Potentially, a thread could even be used to do time-based eviction policies. However, here either a lock would have to be used, or the current STM system would have to be modified to allow for STM transactions to run in unsafePerformIO, something that is currently unsupported.

With the new concept of Type Families, it would even be possible to choose an appropriate data-structure based on the key-type, to guarantee optimal performance.

Blog move

As much as I like blogger, and the fact that I can use my google account, I have finally decided that I will be moving to a new wordpress blog.

I will see how this experiment goes. This blog and the old entries will remain here, and if at some future point I find wordpress unsatisfactory, I can always come back.

One thing that I will miss is the the fact that in blogger I could insert javascript to use analytics.google.com. However, I disliked certain minor things about blogger. For instance the incredible amount of whitespace it would add between list items as well as before or after code-snippets. I also disliked the supported designs, though granted, that could be tweaked.

WordPress feels very snappy and fresh, and it seems to come with built-in latex support. We will see where this new blog goes and whether I decide to stay there or return here. However, for now I feel like trying it out.

Blog move

As much as I like blogger, and the fact that I can use my google account, I have finally decided that I will be moving to a new wordpress blog.

I will see how this experiment goes. This blog and the old entries will remain here, and if at some future point I find wordpress unsatisfactory, I can always come back.

One thing that I will miss is the the fact that in blogger I could insert javascript to use analytics.google.com. However, I disliked certain minor things about blogger. For instance the incredible amount of whitespace it would add between list items as well as before or after code-snippets. I also disliked the supported designs, though granted, that could be tweaked.

WordPress feels very snappy and fresh, and it seems to come with built-in latex support. We will see where this new blog goes and whether I decide to stay there or return here. However, for now I feel like trying it out.

Free Hugs Campaign

While I usually tend to avoid posting blog-entries on non-technical stuff, mostly because I do not think that I would add much to the world by hyping about the latest thing, I will have to make an exception.

I found the following movie on Youtube and found it very touching. Granted, the music does add an emotional overtone to it all that makes it all the more touching. If I weren’t so shy in public, I’d try something similar. I think it’s a great idea and it certainly brought a smile to my face. The story in the sideline regarding it is also quite interesting.

Free Hugs Campaign

Levenshtein Distance in Haskell

Seeing how lately the levenschtein distance is so popular, I thought I’d add a haskell version to the mix.

The code below is pretty self-explanatory, using the typical memoization pattern. I do wonder, however, what would happen if somehow GHC supported lazily-resizable arrays. Perhaps then you could do this on infinite lists and only ask the levenschtein distance up to a certain index.

module Lev whereimport Data.Array

levenshtein :: (Eq a) => [a] -> [a] -> Integer
levenshtein xs ys = arr ! (lenx, leny)
  where arr :: (Array (Int, Int) Integer)
        arr                   = array ((0,0), (lenx, leny))  [((ix, iy), worker ix iy) |
                                                              ix <- [0..lenx], iy <- [0..leny] ]
        lenx                  = length xs
        leny                  = length ys
        arrx                  = listArray (1, lenx) xs
        arry                  = listArray (1, leny) ys
        worker 0      iy      = fromIntegral iy
        worker ix     0       = fromIntegral ix
        worker ix     iy      = minimum [1 + arr ! (ix-1, iy), 1 + arr ! (ix, iy-1),
                                         cost ix iy + arr ! (ix-1, iy-1)]
        cost ix iy            = if (arrx ! ix) == (arry ! iy) then 0 else 1

Levenshtein Distance in Haskell

Seeing how lately the levenschtein distance is so popular, I thought I’d add a haskell version to the mix.

The code below is pretty self-explanatory, using the typical memoization pattern. I do wonder, however, what would happen if somehow GHC supported lazily-resizable arrays. Perhaps then you could do this on infinite lists and only ask the levenschtein distance up to a certain index.

module Lev where
import Data.Array

levenshtein :: (Eq a) => [a] -> [a] -> Integer
levenshtein xs ys = arr ! (lenx, leny)
  where arr :: (Array (Int, Int) Integer)
        arr                   = array ((0,0), (lenx, leny))
                                  [((ix, iy), worker ix iy) |
                                    ix <- [0..lenx], iy <- [0..leny] ]
        lenx                  = length xs
        leny                  = length ys
        arrx                  = listArray (1, lenx) xs
        arry                  = listArray (1, leny) ys
        worker 0      iy      = fromIntegral iy
        worker ix     0       = fromIntegral ix
        worker ix     iy      = minimum [1 + arr ! (ix-1, iy),
                                         1 + arr ! (ix, iy-1),
                                         cost ix iy + arr ! (ix-1, iy-1)]
        cost ix iy            = if (arrx ! ix) == (arry ! iy) then 0 else 1

Lua Serializer

By request, I put the serializer I wrote in lua <a href=”http://www.poucet.org/projects/serializer.lua”>here</a>


It is a serializer I once wrote for a mud I was working on in lua. In the end I got the framework finished but never the game-code. The nice thing of this serializer is that it is possible to define custom serialization functions. I used this with a class-based OO system where I would serialize classes by name, not by value. That way if I reload the code and then serialize and deserialize my data, I would have the new method-bindings in my objects.

The usage is rather simple:

local f = io.open("somefilename", "w")
local s = serializer.new(f)
s:serialize(mydata, "mydata")
s:flush()
f:close()

It is possible to define custom serialization by defining the __serialize function in the metatable. The function should be named __serialize and take three parameters:

  • value – the value that it is serializing
  • serializer – the serializer to use to write to the file (through serializer:write(…))
  • name – the name of the variable

For example, the following will ensure that the table ‘t’ is always outputted as an empty table. It is important the name is used, as this can be a rather long name (for instance, a field of a field of a table..)

local mt = {}
local t = setmetatable({}, mt)
mt.__serialize = function(value, serializer, name)
  serializer:write(name, " = ", "{}", "\n")
end

Lua Serializer

By request, I put the serializer I wrote in lua on my wiki.


It is a serializer I once wrote for a mud I was working on in lua. In the end I got the framework finished but never the game-code. The nice thing of this serializer is that it is possible to define custom serialization functions. I used this with a class-based OO system where I would serialize classes by name, not by value. That way if I reload the code and then serialize and deserialize my data, I would have the new method-bindings in my objects.

The usage is rather simple:

local f = io.open("somefilename", "w")
local s = serializer.new(f)
s:serialize(mydata, "mydata")s:flush()f:close()

It is possible to define custom serialization by defining the __serialize function in the metatable. The function should be named __serialize and take three parameters:

  • value – the value that it is serializing
  • serializer – the serializer to use to write to the file (through serializer:write(…))
  • name – the name of the variable

For example, the following will ensure that the table ‘t’ is always outputted as an empty table. It is important the name is used, as this can be a rather long name (for instance, a field of a field of a table..)

local mt = {}
local t = setmetatable({}, mt)
mt.__serialize = function(value, serializer, name)
  serializer:write(name, " = ", "{}", "\n")
end

Update

Next month I start at Google in Zurich. Been busy with trying to finish my phd, though it seems I will still have some writing left to do after I start my new job. Anyways, I’m definitely excited about this opportunity.

The fact I’ve been busy explains the silence on my blog. But here, in the spirit of A Faster Fibonacci here is a quick Haskell version. I will leave the explanation for the other blog post. Basically the execution is quadratic, and memoization is used to speed it up even more by removing duplicate calculations:


module Main where
import Data.Array

fib n = arr ! n
where arr = array (0,max 2 n) $ [(0,0), (1,1), (2,1)] ++
[(i, val i) | i <- [3..n]]
val i = let x = i `div` 2
in (arr ! x) * (arr ! (i - x - 1)) +
(arr ! (x + 1)) * (arr ! (i - x))

Update

Next month I start at Google in Zurich. Been busy with trying to finish my phd, though it seems I will still have some writing left to do after I start my new job. Anyways, I’m definitely excited about this opportunity.

The fact I’ve been busy explains the silence on my blog. But here, in the spirit of A Faster Fibonacci here is a quick Haskell version. I will leave the explanation for the other blog post. Basically the execution is quadratic, and memoization is used to speed it up even more by removing duplicate calculations:

module Main where
import Data.Array

fib n = arr ! n
  where arr   = array (0,max 2 n) $ [(0,0), (1,1), (2,1)] ++
                                    [(i, val i) | i <- [3..n]]
        val i = let x = i `div` 2
                  in (arr ! x) * (arr ! (i - x - 1)) + (arr ! (x + 1)) * (arr ! (i - x))