caffeinatedcode.wordpress.com Open in urlscan Pro
192.0.78.13  Public Scan

Form analysis
2 forms found in the DOM

POST https://subscribe.wordpress.com

<form method="post" action="https://subscribe.wordpress.com" accept-charset="utf-8" style="display: none;">
  <div>
    <input type="email" name="email" placeholder="Enter your email address" class="actnbr-email-field" aria-label="Enter your email address">
  </div>
  <input type="hidden" name="action" value="subscribe">
  <input type="hidden" name="blog_id" value="2642107">
  <input type="hidden" name="source" value="https://caffeinatedcode.wordpress.com/">
  <input type="hidden" name="sub-type" value="actionbar-follow">
  <input type="hidden" id="_wpnonce" name="_wpnonce" value="0f37710795">
  <div class="actnbr-button-wrap">
    <button type="submit" value="Sign me up"> Sign me up </button>
  </div>
</form>

<form id="jp-carousel-comment-form">
  <label for="jp-carousel-comment-form-comment-field" class="screen-reader-text">Write a Comment...</label>
  <textarea name="comment" class="jp-carousel-comment-form-field jp-carousel-comment-form-textarea" id="jp-carousel-comment-form-comment-field" placeholder="Write a Comment..."></textarea>
  <div id="jp-carousel-comment-form-submit-and-info-wrapper">
    <div id="jp-carousel-comment-form-commenting-as">
      <fieldset>
        <label for="jp-carousel-comment-form-email-field">Email (Required)</label>
        <input type="text" name="email" class="jp-carousel-comment-form-field jp-carousel-comment-form-text-field" id="jp-carousel-comment-form-email-field">
      </fieldset>
      <fieldset>
        <label for="jp-carousel-comment-form-author-field">Name (Required)</label>
        <input type="text" name="author" class="jp-carousel-comment-form-field jp-carousel-comment-form-text-field" id="jp-carousel-comment-form-author-field">
      </fieldset>
      <fieldset>
        <label for="jp-carousel-comment-form-url-field">Website</label>
        <input type="text" name="url" class="jp-carousel-comment-form-field jp-carousel-comment-form-text-field" id="jp-carousel-comment-form-url-field">
      </fieldset>
    </div>
    <input type="submit" name="submit" class="jp-carousel-comment-form-button" id="jp-carousel-comment-form-button-submit" value="Post Comment">
  </div>
</form>

Text Content

CAFFEINATED CODE


 

 


SIMPLE LATEX CTAGS AND TAGLIST

•November 16, 2009 • 3 Comments

Just a quick update because I find this incredibly useful


CTAGS

Exuberant ctags is a great tool for navigating code. Unfortunately it does not
have support for latex. You can add the following code to ~/.ctags to add
support for some simple latex tags:

--langdef=latex
--langmap=latex:.tex
--regex-latex=/\\label\{([^}]*)\}/\1/l,label/
--regex-latex=/\\section\{([^}]*)\}/\1/s,section/
--regex-latex=/\\subsection\{([^}]*)\}/\1/t,subsection/
--regex-latex=/\\subsubsection\{([^}]*)\}/\1/u,subsubsection/
--regex-latex=/\\section\*\{([^}]*)\}/\1/s,section/
--regex-latex=/\\subsection\*\{([^}]*)\}/\1/t,subsection/
--regex-latex=/\\subsubsection\*\{([^}]*)\}/\1/u,subsubsection/


This adds tags for sections, subsections, subsubsections and labels. Even though
this is very basic, I find it’s all I need for editing latex documents.


TAGLIST

taglist is a nice plugin for vim which autogenerates tags using exuberant-ctags
and can list all the tags in a file in a separate window.

You can add latex support to it by adding this line in your ~/.vimrc (assuming
you have already added the code given above to .ctags)

let tlist_tex_settings =
'latex;l:labels;s:sections;t:subsections;u:subsubsections'


Also, since I use the ‘-‘ and ‘:’ characters a lot in my labels, I find it
useful to add those characters to iskeyword

set iskeyword=@,48-57,_,-,:,192-255

iskeyword defines what characters are considered to be a part of the same word
by commands like ‘w’ and ‘CTRL-]’

That’s it!



Posted in latex, vim


LAZINESS AND DYNAMIC PROGRAMMING

•March 26, 2009 • 3 Comments

Recently I was thinking about purely functional solutions to dynamic programming
problems. The problem with the conventional, imperative technique for solving
such problems is that it assumes the existence of O(1) access arrays. So
translating the code directly using purely functional data structures is going
to add an extra factor of log(n).

Originally this started out as a purely academic exercise since one can always
use mutable arrays in Haskell. However it turns out that there is a purely
functional approach that is just as fast, and really quite elegant.



THE CHAIN MATRIX MULTIPLICATION PROBLEM

I chose this to start with since its standard, and simple (In all this I’m going
to assume you know the imperative solution. If not here it is). My initial idea
was to do something like the following. First consider the Fibonacci function:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


Everyone knows how slow this is. But it’s easy to speed up (Edit:fixed!):

fib n = fst $ foldl (\a b -> (fst a + snd a, fst a)) (1, 0) [1..n]


I was wondering if something similar could be done with chain matrix
multiplication. The idea is that although they are called random access arrays,
the actual order of accesses is far from random! So I wanted to see if, given
the recursive solution, I could determine the order of accesses and use that to
transform the recursive solution into a fold-like form.

For chain matrix multiplication, the order of accesses is something like this:
The value of a cell in the memo table depends on the minimum of the sums of the
corresponding elements in the column below and the row to its left. So you focus
on a cell and the corresponding row and column. You can calculate the value in
the cell by zipping the corresponding row and column together with (+), and
taking the minimum. Then you move to the next cell. Now your focus must change
to the appropriate row and column (efficiently!), using what is essentially a
type of zipper

So I wrote a purely functional program in Haskell that juggled things
appropriately so as to be O(n^3) (which is the time-complexity of the imperative
version). It can be done, and all you need are lists. However the result is not
very nice, because everything must fit together just so. It works but its not
really very satisfactory.

Now the juggling required for this problem is bad enough, but to make matters
worse there would have to be a different solution to each DP problem. Actually,
things are much worse than that. There will be some problems where the order of
accesses will depend on the specific instance of the problem (eg Job scheduling
as long as the jobs aren’t all of unit time). It is of course possible that even
these can be transformed into a form where a strict, efficient, purely
functional program can be written but it will certainly be far too messy a
solution to what was once a simple problem.



LAZINESS

Notice how I snuck in the word “strict” in the previous sentence. It turns out
that in a lazy language, the solution is simple. Because of the problems
mentioned above, I started looking for alternatives. If I wanted to solve the
problem efficiently using just lists, I needed to regulate the order of accesses
which seemed to be impossible. So then I wondered if there might be a way of
forming an acceptable data structure for arrays, or rather an alternative data
structure that is “good enough” for the current problem.

It turns out that no fancy alternative is needed. An immutable array will work
just fine! The key here is that even in the imperative world, we are writing to
the array just once. An immutable array can be “written to” once – when
initializing it. In a strict language this doesn’t help much. But with laziness
you can build up an immutable array recursively.

I’ll explain through an example. Lets take fibonacci. This is not usually
considered a DP problem, but anyway:

fib n = fib' n
  where
    memo = array (0, n) [(i, fib' i) | i <- [0..n]]
    fib' 0 = 1
    fib' 1 = 1
    fib' i = memo!(i-1) + memo!(i-2)


Notice that we never update the array. It starts out with the correct values
already! Within fib' I’m using memo in place of the recursive calls to fib'.
Each element of memo gets initialized to the correct value the first time its
accessed. If it’s accessed more than once, then the other calls to memo!i will
return immediately, since the value has been calculated and stored already. In
effect, laziness is giving us a “one-time-write” array.

Now its trivial to extend this example to any recursive function. Coming back to
chain matrix multiplication:

matrix dim = matrix' (1, n)
  where
    n = snd $ bounds dim
    memo = array ((1,1), (n, n)) [((i, j), matrix' (i, j)) | i <- [1..n], j <- [i..n]]

    matrix' (i, j)
      |i == j = 0
      |otherwise = foldl1 min 
        [memo!(i,k) + (dim!(i-1) * dim!k * dim!j) + memo!(k+1,j) | k <- [i..j-1]]


Here dim is an array containing matrix dimensions so that the dimensions of the
i’th matrix are dim!(i-1) x dim!i.



MORAL!

When solving a DP problem, the usual technique is to first write a recursive
solution, and then convert it into an efficient solution by building up a table
of intermediate values. The cool thing about the technique I described above is
that the second step of this process becomes trivial. The solution is just a
memoized version of the recursive solution, and hence easier to understand than
the usual imperative solution (you can compare on wikipedia). The memoization is
almost implicit. There is no need to check whether a value has been computed or
not. We just use it, and laziness handles the rest.

The transformation from basic recursive to memoized is also a simple one. In
fact it shouldn’t be hard to automate this transformation (perhaps in Template
Haskell), but even manually this is easy and gives a nice, clean solution.

Of course, I’m sure people have thought of this before, but it seemed new to me
because I think deep down I’m still stuck in a “strict” mindset. Hopefully it
was just as non-obvious to people reading this! For me it was a reminder that
some very cool things are possible in lazy languages once you start grokking
them.



Posted in functional, Haskell, programming


FUNCTIONAL PEARLS 2.5 – DERIVATIVES OF TYPES

•October 22, 2008 • Leave a Comment

This post is not only extremely late, its also a bit of a cop-out. Last time I
said I would write about derivatives of types. This is a cop-out in the sense
that its a bit more “overview”-ish than I would have liked, but I did not find a
way around that without making the whole thing unacceptably long. So think of
this as a way to get a feel for what’s going on, and if you want more details
you can always look at the paper


ZIPPERS AGAIN

We’ll start with a simple binary tree:

data BTree = Leaf | BTree (BTree, BTree)


Notice that this is a “bare” tree – only structure, no data. But it will do for
our purposes. Now you’ll remember that in a Zipper, we had a subtree which was
the focus of attention, and a Path which represented “everything else”. The Path
itself was a series of steps, going one level down at a time. It is this notion
of “step” that we are going to capture i.e. how do you represent the “context”
of an immediate subtree of this tree. You can then do this multiple times to get
the complete Path used in the zipper.

This should be clearer by refering to the BTree example. The “step” type here
is:

Bool * BTree


The Bool tells us whether we are in the left or the right branch, and the BTree
is the other branch i.e. the one we didn’t take. The Path essentially consists
of a series of these steps, one for each level that we have descended.

Now lets be a little loose and write the definition for BTree as follows:




or




Here we are ignoring the data constructors, and just thinking about the types
themselves. And here’s the trick: Think of this as an algebraic expression, and
differentiate it wrt (which is now a variable in this expression) as you would
have in high school.




But Bool = True | False or in our notation 1 + 1. This means that the
“derivative” has given us exactly the step type we were looking for!

This was not just a lucky example. McBride found that the rules of
differentiation can be applied (unchanged) to types (including rules for
products, the chain rule etc.), and they always gave the “correct” step type.
That good ol’ Leibniz should have anything to say about type theory is really a
remarkable coincidence. Or is it?


DETAILS, DETAILS

Now in the above section (and too an extent in this entire post) I’ve glossed
over some things which are worth going into. For example, what sort of types can
we differentiate? (“regular” types) Functional types as well? (no). What exactly
does differentiation mean? The notation I am using to describe types also needs
to be explicitly defined, we need to worry about variable capture, etc. etc. I
cannot go into all that here, but hopefully the notation makes sense intuitively
so I’ll only deal with some of the details.

I had asked you to accept that a BTree could be defined as . This is in fact
incorrect, because doesn’t make too much sense (and in fact tempts me to solve
the quadratic and conclude that or some such!).

McBride defines such recursive types using a least fixed point




But then, why did I differentiate instead of ?

Here’s why: Taking a derivative is more general than calculating a step type
(think about non-recursive types. “Step type” is meaningless there, but you can
still take a derivative). What really does, is it punches a “hole” for an
element in a container . This gives us the “context” or the surroundings of that
element – i.e. the hole tells us where this element “fits” into the larger type.
For recursive types like BTree suppose we punch a hole at a particular level (in
this example, in ). Here, the container is one level in the tree, and the
element is the immediate subtree. By punching a hole for this element we get
what we’ve been calling the “step type”. So for step types we don’t
differentiate the tree, but rather one level of the tree.

Just to make this clearer, consider the type [String]. We can represent this
with a fixed point:




Now, I haven’t given you the differentiation rule for (the chain rule is
involved here!) so accept for the moment that:

d[String]/dString "is isomorphic to" [String]*[String]


Where “is isomorphic to” means that syntactically differentiating [String] will
give us an expression which is “essentially the same as” [String]*[String]

Notice that this result makes sense: The context of a String in a list of
Strings should be a pair of strings: the list of its predecessors and the list
of its successors.

On the other hand, [String] is a recursively defined type. So I could consider
its “step type”. This would be:




Again, this makes sense. If a step is a , then a sequence of these steps will
give us back the list of Strings. By the way it makes no sense to differentiate
something of the form with respect to . Why?


DOING THIS FOR REAL

I’ve been busy implementing this in Template Haskell (although for a different
purpose). McBride’s types don’t map directly to Haskell types so there are some
problems, but they’re quite easy to circumvent. For one thing you’ll notice that
McBride dispenses with data constructors, but we have to keep track of them if
we are to “plug in” an element back into its context. But this is not really a
“problem”. There are other niggles such as the fact that McBride does not deal
with parametrized types, or mutually recursive types (directly). On the other
hand something like cannot be expressed directly in Haskell: it will have to be
broken up into something like and (with data constructors).

But really the biggest problem in the implementation has been Template Haskell
itself. Don’t get me wrong: TH is actually quite nice and very, very powerful.
Its just that Haskell AST’s are complicated, and you need a bit of time to get
used to using the TH system (btw if you’re looking to learn TH I recommend
these: http://www.haskell.org/bz/thdoc.htm and http://www.haskell.org/bz/th3.htm
are great).

I guess Lisp’s simpler syntax is a huge gain as far as macro systems are
concerned. Also I’m guessing you wouldn’t get stuck inside the quotation monad
there since impure functions are OK?

Anyway it’ll be some time before I can put up the derivative code since it is a
part of something else, but TH usage has given me some interesting ideas for
other projects. It really is quite powerful!


RECOMMENDED READING

If you want things to be more precise, you’ll have to look at McBride’s paper.
You might also want to look at “dissection” of types, which is the next logical
step in a sense. But in any case, I highly recommend this post on sigfpe’s
excellent blog. It really makes you think about how deep this connection between
might be. Is it all just an artifact of our notation? Which of the results and
concepts from differential calculus have meaning in the world of types? Could we
assign some meaning to integration (other than just inverse differentiation)?
Some pretty interesting questions here – any answers?

Posted in functional, functional pearl, Haskell


FUNCTIONAL PEARLS #2: THE ZIPPER

•September 9, 2008 • 4 Comments

Well I’m back with part two of my functional pearls series. This pearl is
perhaps the most famous: Gerard Huet’s Zipper. Its a simple, but beautiful
little data structure for purely functional tree editing.


THE PROBLEM

You have to create an application which involves manipulating trees of some kind
(Huet wanted to make a structured editor for a proof assistant – whatever that
means!). You want to be able to move about in a tree, change things etc. You
want it to be efficient, but you don’t want to do evil mutable things.

With that background, let’s start with a variable arity tree type:

data Tree a = Leaf a | Tree (a, [Tree a])


Now we’re going to construct a Zipper for such trees. We want tree editing of
course, but I am going to focus on navigation within the tree. If you can do
that, then editing is easy.

One way of “moving about” within such a tree is obvious: I start at the top and
go down to whatever spot I’m interested in. This is perfectly fine if my moves
are going to be entirely random because in that case no matter what I do I will
have to work arbitrarily hard to get where I want to go, so this solution is as
good as any. However, tree editing is rarely that random.

Usually after I work on a node, I am likely to move to one of the nodes nearby.
So it would be great if I had an efficient way of moving up/down/left/right from
the current node (instead of always starting at the root). This means I must
have a way to remember where I am right now and how I got there. In a nutshell,
thats all the zipper is: a way to keep track of location within a tree in order
to provide efficient movement and editing operations around the ‘current’
location.


LOST!

So we will perform operations not on a tree, but on a ‘location’

data Location a = (Tree a, Path a)


Location is a tuple of two things: a (sub)tree which is the current focus of
attention, and a path upwards from the root of this subtree to the root of the
entire tree. This path must have all the information needed to build up the rest
of the tree whenever needed. For example, if I want to move up, I need to be
able to build my parent’s subtree again. So we define:

data Path a = Top | Node (a, [Tree a], Path a, [Tree a])


Basically, this says: If I am (the root of) a subtree, I need to know four
things – My siblings on the left and on the right, my parent’s label (in order
to build the parent again), and a path to my parent. This is what a ‘Node’
stores (Top simply means there is nothing above me). Then working recursively
upward, I can build up the entire tree.

This is where the Zipper gets its name. It works a lot like a physical zipper
(except inverted). When moving down to a subtree, you are “zipping up” the rest
of the tree into a ‘Path’. When you move up, you “pull down” the zipper to
reveal… the rest of the tree!

OK, now lets look at a navigation operation – moving one step left/right:

goLeft (t, Node (a, tl:l, p, r)) = (tl, Node(a, l, p, t:r))
goRight (t, Node (a, l, p, tr:r)) = (tr, Node(a, t:l, p, r))


(Of course all other patterns are errors.) Both operations are simple, the only
thing to note is the ‘direction’ of the left and right sibling lists ‘l’ & ‘r’.
The immediate left (resp. right) sibling is at the head and the lists then move
‘outward’ from there. This ensures constant time movement in both directions.

Moving down is also constant time, moving up however is not:

goDown (Tree(a, t:r), p) = (t, Node(a, [], p, r))
goUp (t, Node(a, l, p, r)) = (Tree (a, reverse l ++ (t:r)), p)


With these basic navigation primitives, we can define more complicated
movements. Insertions and deletions are also similar (code given later). There
can also be a few variations on this zipper: Huet gave an example of a
‘memoizing’ zipper, which is useful when you want to go up and down to the same
spot often. Here, the tree would be defined as:

data MemoTree a = Leaf a | Tree (a, [MemoTree a], MemoTree a, [MemoTree a])


A MemoTree keeps track of a certain distinguished subtree at each level. The
definitions of ‘Path’ and the ‘goUp’ and ‘goDown’ primitives are changed
slightly, so that goUp . goDown = id i.e. goDown doesn’t take you to the
leftmost child, but rather to the exact same child you went up from (hence the
MemoTree a in the Tree constructor).


GENERICIZE?

Now this is all well and good, but there is something fundamentally
unsatisfactory here: we are forced to use variable arity trees. Suppose I had a
binary tree instead.

 
BTree a = Nil | BTree (a, BTree a, BTree a) 


How would I obtain a Zipper for this? Of course, it is easy to modify the code
for a variable arity Zipper and make it work with BTrees. But this is not good
enough because I would have to (manually) create a new Zipper for every tree
type. Can I generate these Zippers automatically? Alternatively, can I write a
single Zipper that will work for any tree type?

We have now entered Conor McBride territory. If you want to generate a Zipper,
then given a tree you must define a Path type. McBride found a wonderful
connection between ordinary, high school derivatives, and Zipper types. I will
talk about this in my next post (or you could read McBride’s “The derivative of
a regular type is it’s type of one hole context”), but its too long (and too
interesting) to fit here.

Right now I’m going to take a different (and very simplistic) route. Here you
will find a Zipper module (largely untested btw) which is a very simple hack
based on the variable arity Zipper. It exports a single class, Zippable, that
can be instantiated by a fixed arity tree to automagically get a Zipper for that
tree.

class Zippable tree a | tree -> a 


(You might want to look up multi-parameter type classes and functional
dependencies, but you don’t really need to. the tree -> a part simply means that
when instantiating this class, the ‘tree’ type will uniquely specify an ‘a’
type. It’s only needed to remove ambiguities when type checking).

Here tree is your tree type (eg BTree String) and a is the element type (eg
String). To create a Zippable instance, you must define the following functions
(the navigation/editing defaults can then be used):

fromList :: (a, [tree]) -> tree
toList :: tree -> (a, [tree])
isNil :: tree -> bool
nil :: tree
arity :: tree -> Int


And here’s a BTree Zipper:

instance (BTree a) a where
  fromList (a, [l,r]) = BTree (a, l, r)
  toList (BTree (a, l, r)) = (a, [l,r])

  isNil Nil = True
  isNil _ = False
  nil = Nil
  arity _ = 2


fromList is used to make it look like the current node is variable arity. toList
does the opposite. Internally, all tree editing functions maintain a constant
number of trees at each level (by inserting/deleting ‘nils’ which act as
placeholders: which is why the nil function is needed to return a ‘nil’ value).
The arity represents arity (doh!), and currently its not really used except that
setting it to 0 is used to specify variable arity.

Now one obvious problem here is that this really only works for types like
‘BTree’, i.e. your tree must be representable in this particular form. This need
not be the case for even slightly more exotic trees (for eg. where there may be
several branches of different types). So lets restrict ourselves to these simple
tree types for now.

The module hides the definition of Path and Location, but provides two functions
tree and root which take a tree in and out of a Zipper. So externally, your
program only sees your tree type. Obviously, the whole thing is just an ugly
hack, but to an extent it works!
For example:

(>>>) = flip (.)
edittree :: (Zippable (BTree a) a) => a -> BTree a -> BTree a

edittree a = (tree >>> goDown >>> changeLabel a >>> goUp >>> root)


There may also be scope for some fun variations, because you may be able to play
around with fromList. Perhaps perform height balancing – fromList only gets
called when moving up, or inserting below the current position. Another
interesting question is whether you could define suitable fromList and toList‘s
for non-tree structures. Perhaps a Zipper for a graph which works on say, its
(implicit) DFS tree? Of course I’m not at all sure this is possible, or that it
makes any sense at all

Anyway, that’s it for now, next time I’ll talk about what derivatives have to do
with data types, and a more serious solution to the generic zipper problem.

Posted in functional, functional pearl, Haskell, programming


FUNCTIONAL PEARLS #1: FOLDR AND CPROD

•August 20, 2008 • 4 Comments


PEARLS: A PROGRAMMERS BEST FRIEND?


So, I’m back after a really long hiatus. This post is part 1 of a series about
well known and perhaps not-so-well-known functional pearls. A Functional Pearl
is an elegant, purely functional solution to a problem. In this post, we’ll look
at the earliest known functional pearl, Christopher Strachey’s Cartesian product
function. I found this pearl in a paper called “Strachey’s functional pearl,
forty years on” by Mike Spivey, and this post is largely based on that paper.



FOLDS


If you’ve written any amount of code in a functional programming language,
you’ve come across foldr (or perhaps foldl). It’s ubiquitous in the fp world and
as natural as say, a for loop in an imperative language.
foldl y [x1,x2,x3,..., xn] = f(f(...f(f(x1, y), x2), ...), x_n)
And foldr is the same, but “from the right”:
foldr f y [x1,x2,x3, ..., xn] = f(x1, f(x2, f(..., f(xn, y)...)))

Incidentally, a nice way of looking at foldr is: it is the unique solution (for
fixed f and o) to the equations:

foldr f o [] = o
foldr f o (x:xs) = f x (foldr f o xs)

One of the things that are so great about languages like Haskell, is that this
IS how you define functions. The above is executable Haskell code that defines
foldr!



AND GOD SAID: LET THERE BE FOLDR…


A bit of history about foldr. It came as something of a shock to me that foldr
was invented (discovered?), and there was actually a time without a foldr!
Somehow I had always assumed that foldr had been created in the Big Bang along
with everything else. But it appears that there was actually a time when higher
order functions like “map” were known (in LISP, for example) but foldr wasn’t.
And although a lot of programmers had probably written their own foldr’s without
realizing it, the discovery of its coolness and universal usefulness can
probably be attributed to Christopher Strachey (I should clarify that the
history is actually pretty hazy, so please tell me if you can find an earlier
reference)

He’s probably better known as one of the developers of the CPL programming
language (the great-grandfather of C). But he’s done a bunch of other things in
his career, and among them lies the first functional pearl.

He was investigating foldl and foldr (although not by that name) in 1961
(according to some handwritten notes that were found later) and began to realize
how useful these functions could be. Then, in 1966 he published a paper giving
examples of CPL code written in a functional style. This paper contained (among
many other things) a function called cprod, which used foldr. This is the
function that is now widely regarded as the very first “functional pearl”.



A X B = ?


The cprod function finds the Cartesian Product of a bunch of sets (expressed as
a list of lists). For example,
cprod [[1,2],[2,3],[1]] = [[1,2,1], [1,3,1], [2,2,1],[2,3,1]]
These days, several languages let you do this sort of thing with list
comprehensions. For example,
cprod (xs:xss) = [x:ys | x <- xs, ys <- cprod xss]

But we will use neither list comprehension nor recursion – just foldr. To see
how, remember what I said about p = foldr f o being the unique solution to:

p [] = a
p (x:xs) = f x (p xs)

Then for f xs yss = [x:ys | x <- xs, ys <- xss], cprod can be seen as the unique
solution to:

cprod [] = [[]]
cprod (xs:xss) = f xs (cprod xss)


In fact, cprod = foldr f [[]]. Now all we have to do is rewrite the list
comprehension f in terms of list primitives alone. We can do this by expanding
each generator in the comprehension as a foldr, giving:

cprod = foldr f [[]]
  where 
     f xs yss = foldr (g yss) [] xs
     g yss xs xss = foldr (h x) xss yss
     h x ys uss = (x:ys):uss


Beautifying this a little, we get our very first functional pearl!

cprod = foldr f [[]]
  where 
    f xs yss = foldr g [] xs
      where 
        g x xss = foldr h xss yss
          where h ys uss = (x:ys):uss


Next week – zippers!


Posted in functional, functional pearl, Haskell, programming


EXTENDING SML’S LISTS

•June 12, 2008 • Leave a Comment

I’ve been busy working on a project in SML/NJ, and in the process I ended up
writing a few generic list functions. I’ve extracted these into a separate
module, and I’m putting it up here. Warning: These are just quick hacks (but
they work (I think!)), and not all of them will be useful outside of my project.

Briefly, here’s what this contains:
A specialized version of foldl, a join function similair to Ruby’s, list
generating functions and range functions, map and app functions that also pass
in the index of the element, and a special kind of cross product function.

Anyway here goes (sorry for the meaningless syntax highlighting, SML/NJ is of
course not supported by the WordPress sourcecode plugin):

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
81
82
83
84
85
86
87
88
89
90
91
92
93
structure ListExtension = struct
  exception InvalidArgument of string;
 
  (*
  * folds left across a list, applying a binary function pairwise to its
members.
  * Eg, foldLeft f [a,b,c] = f(f(a,b),c);
  *)
  fun foldLeft f [] = raise InvalidArgument "Empty list to foldLeft"
    |foldLeft f (h::[]) = h
    |foldLeft f (h::t) = foldl (fn (a,b) =&gt; f (b,a)) h t
 
  (*
  * 'joins' a list into a string, converting each member into a string by the
  * given function, and interspersing the given string
  *)
  local
    fun join_aux s f (h::t) res =
        if res = "" then
          join_aux s f t (f h)
        else
          join_aux s f t (res ^ s ^ (f h))
      |join_aux s f [] res = res
  in
    fun join s f h = join_aux s f h ""
  end
 
  (*
  * Convenience function when the conversion is identity
  * eg joinString "+" ["a", "b", "c"] = "a+b+c"
  *)
  fun joinString s h = join s (fn a =&gt; a) h
 
  (*
  * List generators.
  *)
  local
    fun step_aux n inc lim f l =
      if (inc > 0 andalso n > lim) orelse
         (inc < 0 andalso n < lim) orelse
         (inc = 0) then
        l
      else
        step_aux (n + inc) inc lim f ((f n)::l)
  in
    fun step start fin inc f =
      if start <= fin then
        List.rev (step_aux start inc fin f &#91;&#93;)
      else
         List.rev (step_aux start (~inc) fin f &#91;&#93;)
  end
   
  fun downfrom n f = step n 0 1 f
  fun upto n f = step 0 n 1 f
  fun fromto start fin f = step start fin 1 f
    
  fun range from to = ste from to 1 (fn i => i)
  fun rangeStep from to inc = step from to inc (fn i => i)
 
  (*
  * Map with index. Same as List.map, but also passes in the index as an
  * argument to the given function
  *)
  local
    fun mapi_aux f [] i res = (List.rev res)
      |mapi_aux f (h::t) i res = mapi_aux f t (i+1) (f (i,h)::res)
  in
    fun mapi f l = mapi_aux f l 0 []
  end
  
  (*
  * app with index. Same as List.app, but also passes in the index as an
  * argument to the given function
  *)
  local
    fun appi_aux f [] i = ()
      |appi_aux f (h::t) i = (f (i, h); appi_aux f t (i+1))
  in
    fun appi f l = appi_aux f l 0
  end
 
  (*
  * Applies the function f to each element of the cross product of the two
  * lists.
  * f(a,b) is discarded if it is NONE, if it is SOME(c) then c is added to the
result
  *)
  local
    fun crossProduct_aux f (h::t) l result =
      crossProduct_aux f t l ((List.mapPartial (f h) l) @ result)
      |crossProduct_aux f [] l result = result
  in
    fun crossProduct f (a, b) = crossProduct_aux f (List.rev a) b []
  end
end

Suggestions/ additions are welcome of course.

Posted in code, functional, programming, sml


UBUNTU HARDY UPGRADE PROBLEMS

•April 27, 2008 • 10 Comments

I got hardy yesterday, and the upgrade wasn’t without problems. I’m posting my
solutions here: hopefully they’ll help someone else.


NVIDIA

First, Ubuntu wouldn’t let me upgrade, saying “Couldn’t calculate upgrade”. A
peek at the logs (at /var/log/dist_upgrade/) revealed that this was because of
nvidia-glx. It needed to be removed (because there is now a nvidia-glx-new), but
it was in the removal blacklist. So I thought I’d do this manually. I removed
nvidia-glx and installed nvidia-glx-new with apt, and then tried upgrading
again.
I consider this a bug in the upgrade system. The installer should at least tell
me that this might be the issue, and that I should consider changing my drivers,
because if I hadn’t known about the existence of nvidia-glx-new, the log alone
would have been of no use.

Ok, having done that I tried dist-upgrade’ing again. This time it looked like it
was going to work. But then it threw up errors about nvidia-glx-new, and every
single xorg package. I tried reinstalling nvidia-glx-new, but dpkg didn’t let me
(I kept getting “subprocess post-removal script returned error exit status 2”).
Google led me to this:

sudo dpkg-divert --remove /usr/X11R6/lib/libGL.so.1
sudo dpkg-divert --remove /usr/X11R6/lib/libGL.so.1.2
sudo dpkg-divert --remove /usr/lib/xorg/modules/libGLcore.so

However dpkg-divert gave me “No such file or directory” for each of the
libgGL’s. After some headscratching, I realized the reason was that there was no
‘lib’ directory in ‘/usr/X11R6’. So a ‘mkdir /usr/X11R6/lib’ and then
dpkg-divert –remove fixed the problem.
I still don’t understand how this happened in the first place – I’m just happy I
got it to work.


TERMINAL FONTS

After hardy was installed I noticed that my Terminal had stopped antialiasing
its fonts. Here’s the fix:

cd /etc/fonts/conf.d
sudo rm 10-hinting-medium.conf
sudo rm 10-no-sub-pixel.conf
sudo ln -s ../conf.avail/10-hinting-full.conf
sudo ln -s ../conf.avail/10-sub-pixel-rgb.conf



FIREFOX

Now my one remaining gripe is with Firefox. ff3b5 is highly unstable for me. I
used Beta 4 up until now, and that worked just great. beta 5 has crashed on me 4
times just while writing this blog post! (although that’s an extreme case.. it
isn’t that bad normally).
However, I may have found a solution. I’m beginning to think its firebug that’s
causing the crashes, but I’m not sure yet. Any other ideas?

Posted in ubuntu


HASKELL ? : THE TERNARY OPERATOR

•April 11, 2008 • 4 Comments


? :: Bool -> (t, t) -> t
a ? (b, c) = if a then b else c

And there you have the Haskell ternary operator. Nice syntax, and lazy
evaluation means that only one of b or c is ever evaluated!

Posted in code, Haskell


SIMPLE JAVASCRIPT PROGRESS BAR

•April 8, 2008 • 11 Comments

Here’s a quick and obvious-in-hindsight progress bar that I created while
working on a project:

1
2
3
<div id="progress" style="border: 1px solid black;">
  <div style="background-color:green; width:50%">&nbsp;</div>
</div>

Now just use Javascript to change the width of the inner div!

Of course there can be any number of variations on this theme. For example, a
repeating background-image can give a nice effect.

Or how about a discrete bar instead with say, five stars? Just use five image
tags, then if you have these image elements in the array ‘stars’:

progress = Math.round (progress/20); //progress was a percentage
for (i =0; i < progress; i++) stars[i].src = "filled_star.gif"; for (i =
progress; i < 5; i++) stars[i].src = "empty_star.gif"; [/sourcecode]

Posted in code, javascript, web


A LOOK AT GOBO LINUX

•March 26, 2008 • Leave a Comment

I came across an interesting Linux distro today, called GoboLinux. Gobo brings
about a radical change in the way your filesystem is organized. Instead of
having your programs scattered all over, Gobo organizes the filesystem in a much
more sane manner (because lets face it, there may be a method to the madness
that is the Linux filesystem, but for most purposes, it’s still madness). In
Gobo, doing an  ls /  will give you:

Programs
Users
System
Files
Mount
Depot

You can easily tell whats going to be where. For example the /Programs directory
has… well all your Programs! But the best part is, if you had two versions of
Foo, they’d be in /Programs/Foo/1.0/ and /Programs/Foo/2.0/. In effect, the
filesystem is now your package manager. Thats a really cool way of looking at
package management. You install a program into /Programs (Gobo comes with a nice
path-agnostic compilation system called “Compile”), and then if you want to
uninstall, just delete its directory. Want to know which program a file
“belongs” to? That’s natural as well, with this hierarchy.

Of course everything cannot possibly be so simple, and Gobo has an uglier side.
First of course, the filesystem-as-package-manager cannot by itself deal with
dependencies. Compile handles dependencies, but if you’re going to slap a
package manager on top anyway, then you’ve lost some of the elegance you gained
with this new filesystem hierarchy.

What’s worse is that Gobo needs to litter all the directories with symlinks to
handle shared files, etc. What’s even worse is that Gobo still maintains the the
traditional hierarchy alongside the new one! Without it, they would go straight
to compatibility hell. So they still have /usr and friends, but these are now
symlinks to their Gobo counterparts. They’ve even made a kernel extension
(called GoboHide) to hide this ugly underbelly from your eyes (GoboHide is not
strictly required, it’s only for hiding the traditional hierarchy).

I can’t help get the feeling that I’ve been sent back to square one :). Of
course, that’s not really true, and my gripes are aesthetic more than anything
else. Gobo really has done something pretty innovative. But wouldn’t it have
been easier to just use fuse to achieve the same goal? Don’t touch the
filesystem hierarchy, don’t make a new distro, just make a filesystem with fuse,
that acts as a different “view” of all your files.

I admit I haven’t thought too much about it, but it seems possible to extend
this to a package manager that would masquerade as a filesystem. You would
certainly be able to get the /Programs coolness, and an rm -rf
/Programs/Foo/1.0, would uninstall version 1.0 of Foo. You might even be able to
manage dependencies within the confines of the filesystem-as-package-manager
paradigm. On the other hand, it could just be a hook into an existing package
manager, and still provide many of the advantages of Gobo. Food for thought, and
perhaps for an interesting project at some point in the future!

As far as Gobo itself goes, I think its great that they’ve done something so
innovative, and I wish them luck. Only problem is, a nicer filesystem hierarchy
is not by itself a strong enough motivation to switch distros (especially since
I’m perfectly happy with my package manager). Maybe as Gobo matures it’ll be
worth looking at again.

Posted in linux

« Previous Entries




RECENT POSTS

 * Simple latex ctags and taglist
 * Laziness and Dynamic Programming
 * Functional Pearls 2.5 – Derivatives of Types
 * Functional Pearls #2: The Zipper
 * Functional Pearls #1: foldr and cprod

bash code functional functional pearl Haskell javascript latex linux programming
rails ruby sml ubuntu vim web

 

Create a free website or blog at WordPress.com.


Caffeinated Code
Blog at WordPress.com.
 * Subscribe Subscribed
    * Caffeinated Code
      
      Sign me up
    * Already have a WordPress.com account? Log in now.

 * Privacy
 *  * Caffeinated Code
    * Customize
    * Subscribe Subscribed
    * Sign up
    * Log in
    * Report this content
    * View site in Reader
    * Manage subscriptions
    * Collapse this bar

 

Loading Comments...

 

Write a Comment...
Email (Required) Name (Required) Website