Back to Questions
1.6k
views8
comments
An interpreter for transformations
f#functional

Hello everybody,

I'm very new to the language and to functional programming in general, coming from a strong imperative/OO background. But I'm fascinated with it. I need help with the following. I'm writing an analyzer for *.reg files. The plan is to scan the .reg file and transform it to a registry tree. I have defined the registry as

type RegistryData =
| Integer of int
| Boolean of bool
| ...

type RegistryItem =
| Data of string * RegistryData // name, value
| Node of string * RegistryItem list // key, data

type Registry = RegistryItem list
Perhaps this is not the best approach but for now I'm going to stick with it. The .reg file is composed of "registry creation commands" so to speak, in effect it's a series of instructions on how to add keys/values to an empty registry. I have managed to parse the file and represent the instructions as a sequence of entries from a discriminated union (e.g. CreateKey of string, ChangeValue of ..., etc). The question now is:How can I transform these instructions to a registry tree? I was thinking of something like an interpreter that interprets each element of the sequence and produces a new tree, e.g.let interpret (commands: seq<RegistryOp>) (tree: Registry) = ...
which should be called recursively starting with the full sequence of operations and an empty tree and calling itself with the tail of the sequence and the transformed tree.But all this sounds too imperative to me. Does anybody know what would the "functional" way of attacking this problem would be? I wouldn't mind starting from scratch, as this is a "pet project". Any help from anybody would be very much appreciated!Cheers,George.

.

I think you have a good strategy. Your interpret function is just a fold, e.g.

let interpret commands tree =
commands |> Seq.fold (fun t c -> ApplyCommand c t) emptyTree

so all you need to do is write the ApplyCommand function that takes a command and a tree and produces a new tree.

[link:msdn.microsoft.com]

By on 1/14/2010 8:20 AM ()

I am also learning how to build a tree(which is immutable) in FP, I would like to chip in my 2 cents that you may like to investigate the Zipper structure which allows efficient 'modification' of a tree.

[link:www.haskell.org]

By on 1/14/2010 10:24 AM ()

Thanks everybody for the replies. I don't know why this doesn't feel right but I'll go for it. I'll try to implement it the way Brian said (Gary, unfortunately your example describes binary trees, which is not my case).

All the meat is in the "ApplyCommand" function. Perhaps I have to revise my tree structure to make things work easier, but I can't convert it to a binary tree because I need to bind it to a WPF treeview. Perhaps somebody could pitch some ideas?

Cheers,
George

By on 1/15/2010 1:25 AM ()

I am sure there is a link some where that has zipper on rose tree(i.e. multiple branches like your structure).

Well the only issue with not using zipper is performance as you would basically need to reconstruct the whole tree(from root).

there is even a generic zipper regardless of your tree structure but that is too abstract for me(involving delimited continuation etc. when I am still struggling with simple continuation) to port to F#.

By on 1/15/2010 12:41 PM ()

I seem to have solved my problem in a purely functional way using various sources of information, mainly from the Haskell Tree structure and partly from Gary's pointers on the Zipper idiom. It seems that a particularly elegant solution to the problem is to:

a) Create a list of the various registry keys in such a way that the tree structure is evident, e.g. ["\HKCU"; "\HKLM"; "\HKCU\Software"; "\HKCU\Software\Microsoft"]
b) Build up the tree using a un-folding function, e.g. Tree.unfold f base
which accepts a function f to produce all the subkeys of a given key from the list of all keys, along with the initial tree.

The problem is producing all the keys in this case. I store them in a seq, but it turns out that a key may be specified multiple times and with a variety of upper- or lower-case combinations. The initial plan of turning the seq into a set and then back into a seq failed miserably because of this: it resulted in lists such as ["\HKCU\software"; "\HKCU\SOFTWARE"; ...]

Does anybody know of an efficient way to filter duplicates out of a sequence? I tried implementing verbatim Haskell's nubBy function, e.g.

let nubBy eq x =
let (|SeqEmpty|SeqCons|) = ...
match x with
| SeqEmpty -> Seq.empty
| SeqCons(x, xs) -> seq { yield x; yield! Seq.filter (...) xs }

but this method does not complete in an acceptable time (it's been running now for 20 minutes on a sequence of ca 7000 elements).

Any pointers would be gladly appreciated. I'd like to use purely functional methods if possible. I want to avoid mutation.

Cheers,
George.

By on 1/19/2010 1:32 PM ()

I can be really stupid sometimes. I just found out about Seq.distinctBy.

By on 1/19/2010 1:39 PM ()

glad you found the needed function.

My experience so far is don't use seq {} to implement functions that are inspired by Haskell in general. Use LazyList instead. Many Haskell functions relies on the implicit lazy and memoization behaviour that is natural to the language and while seq {} can simulate the laziness, it doesn't have the built-in meomization as Haskell. LazyList is more close to that.

By on 1/19/2010 6:17 PM ()

Thanks for the tip Gary! I'll get right on to it!

By on 1/20/2010 5:29 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper