- Haskell-Cafe - Haskell.org

Haskell idioms for hierarchical memory modeling ?
by Dmitri O.Kondratiev 26 May '08

26 May '08

*** How FP in general and Haskell in particular can help in modeling memory with neuron-like structures? *** The particular model discussed here - latter in this text I call it Memory Tree - is a type of neural network (NN) where the network consists of a collection of data processing nodes arranged in a tree-shaped hierarchy. Memory Tree (MT) is a hierarchical classifier, that infers recurring data patterns observed in its input during some period of time T. Time period is a set of discreet times (or moments) T = [t1, t2, ...tN]. Each node reads inputs from all its children and then builds from these inputs a single input vector as a concatenation of children outputs. Node then classifies this newly built input vector assigning it to one of the category groups that node creates. Next node outputs group number that current input belongs to. This output goes to the node parent. All nodes at all all levels do these steps in turn, inputs flowing from bottom level nodes up to a top node through all nodes at all intermidiate levels. Next I illustrate main ideas of MT with a simple example. *** Simple MT Example Primitive MT classifier, used in this example, will (I hope :) discern, for example, these images: 1) ######## ######## ######## ######## 2) ######## #......# #......# ######## 3) ###..### #.####.# #.####.# ###..### ('#' - black dot, '.' - white dot) In my case at each moment MT uses bottom-level nodes to read input from a data file. Input data is a collection of strings. Each string is a binary vector representing data read by some sensor at time tj. For example: v1(t1) : 11111111111111111111111111111111 v2(t2) : 11111111100000011000000111111111 v3(t3) : 11100111101111011011110111100111 ... ... vN(tN) : ... In this example input is 32 bit vector read at consecutive times t1 < t2 < t3 ... tN This vector represents a rectangular view of a camera - 8 x 4 matrix of black (1) and white (0) dots. Shown above images are encoded in 32 bit vectors, one image - one vector, where black dot '#' becomes 1 and white dot '.' becomes 0. In this case MT may have the following topology: -- One Top Level Node: T -- Two Middle Level Nodes: M1, M2 -- Four Bottom Level Nodes: B1,B2,B3,B4 -- Input Vectors: v1(t1), v2(t2), v3(t3), ... vN(tN) To show how nodes in this tree are connected I will use brackets. In my 'bracket notation' parent node name is followed by its child node names in brackets: (T (M1 (B1, B2), M2(B3, B4))) This describes topology where: -- T node has two children: M1 and M2 -- M1 node has two children: B1 and B2 -- M2 node has two children: B3 and B4 (Sorry for poor illustrations, unfortunately I can't use graphics are supported in this post, including ascii art :) For this topology each input vector, for example v1(t2), may be split in four equal parts of 8 bits. Chunks will then represent four regions of the camera image. Each 8 bit chunk is sent as input to the corresponding Bottom Level nodes: B1,B2,B3,B4 v2(t2)_b31-b24 : 11111111 --> B1 v2(t2)_b23-b16 : 10000001 --> B2 v2(t2)_b15-b8 : 10000001 --> B3 v1(t1)_b7-b0 : 11111111 --> B4 To work with these vectors each Bottom node will have dimension of input vector BK = 8 so it can classify 2 ** 8 = 256 input vectors. Let's say Bottom node can classify these 256 input vectors into 2 ** 3 = 8 output groups, so it will have dimension of output vector BL = 3. In turn, each M1 and M2 node will have input dimension equal to the sum of all its children (B nodes) output dimensions: M1K = B1L + B2L = 3 + 3 = 6 M2K = B3L + B4L = 3 + 3 = 6 Our M nodes can classify 2 ** 6 = 64 vectors, and we assume that they can categorize these 64 vectors in 2 ** 2 = 4 groups, so M node output vector is 2 bit long: ML = 2 Connecting two M nodes to a single top node T will requre T input dimension equal to the sum of two M node output dimensions: TK = M1L + M2L = 2 + 2= 4 T node can classify 2 ** 4 = 16 vectors, and we assume T node can group these vectors in 2 groups, so T node output vector is 1 bit long: TL = 1 To summarize: *** Node Attributes Each node in this tree has the following attributes: 1) K-bit input vector. 2) L-bit output vector, where K >= L 3) Node Category Memory (CM) - stores unique category vectors. Each vector is stored as a tuple (V, C) where V is a vector value and C is a category number. Both V and C values, as well as (V,C) pairs are unique for the node. Node can store a limited amount of (V,C) pairs. This amount (CMSize) is equal to the number of categories that node can differentiate and also equal to the node output vector dimension. *** Node Data Processing algorithm: Every Node runs the following endless loop: 1) Read inputs from children 2) Build input vector X 3) Calculate distance between X and every vector in CM and determine if X belongs to any existing node category. If X belongs to existing category Then do step 4) Else If CM is not full create new node category pair (X, C_new) Else return 4) Output vector group number to a higher level node in the tree. *** Main Questions 1) How to model node vector processing and node state? Node receives input and produces output and can change its state by adding new category to Node CM. Will State monad help to 'thread' node state between inputs? I don't see how. State monad encapsulates state transition function: State s a = State (\s -> a, s) that inputs some state value and outputs a pair (value, newState). In my case node category memory (CM) could be such a changing state of node , but what then will be node input vector in State monad? 2) How to traverse classifier tree (MT) so inputs from bottom level nodes could flow up to a top node through all nodes at all intermediate levels? In contrast to a 'normal' tree where all variations of tree traversals start at root node, classifier tree must be traversed starting from bottom level nodes. 3) How to build tools that will allow to construct classifier trees with different topologies? In this case one topology differers from another by a) number of levels and b) numer of children at each level. Ideally I would like to have a simple DSL that will allow specify tree topology declaratively, easy to understand for non-programmer. 4) Most important: In what direction should I look as a Haskell newbie to find answers to these and similar questions? Should I build my own monad to traverse this tree, what other standard monads may help? What combinator libraries should I learn? Will I need Arrows (that at the moment I know only name and nothing more about)? Thanks for reading all this and any help! -- Dmitri O. Kondratiev dokondr(a)gmail.com http://www.geocities.com/dkondr

2 1

what appears to be a persistent problem for me ..
by Galchin, Vasili 26 May '08

26 May '08

Hello, I seem to have recovered from my Ubuntu problems by installing the ghc binary from http://www.haskell.org. However, if I modify a .cabal file, e.g. unix.cabal, then "runhaskell Setup.hs build" is always in the "re-configure" state even if I do a "runhaskell Setup.hs configure" ... It seems the re-configure state is determined by: -- |Check that localBuildInfoFile is up-to-date with respect to the -- .cabal file. checkPersistBuildConfig :: FilePath -> IO () checkPersistBuildConfig pkg_descr_file = do t0 <- getModificationTime pkg_descr_file t1 <- getModificationTime localBuildInfoFile when (t0 > t1) $ die (pkg_descr_file ++ " has been changed, please re-configure.") in /ghc-6.8.2/libraries/Cabal/Distribution/Simple. ?? Kind regards, Vasili

2 1

HaXml and the XHTML 1.0 Strict DTD
by Peter Gammie 26 May '08

26 May '08

Is anyone using HaXml to validate XHTML Strict? The old 1.13.2 version has some bugs in how it handles attributes that stop me from using it. It handled the DTD parsing fine. The most-recent darcs version relies on a newer ByteString than I have, so it is not easy for me to test it. A recent (this year) darcs version failed to parse the DTD, yielding this error: validate: In a sequence: in content spec of ELEMENT decl: head When looking for a non-empty sequence with separators: In a sequence: Expected % but found | in file xhtml1 at line 252 col 50 when looking for a content particle when looking for a content particle This is the context:  <!ENTITY % head.misc "(script|style|meta|link|object)*">  <!ELEMENT head (%head.misc;, ((title, %head.misc;, (base, %head.misc;)?) | (base, %head.misc;, (title, %head.misc;))))> I appreciate any advice on this. cheers peter

3 7

Announce: glome-hs-0.51 (Haskell raytracer, now with type classes)
by Jim Snow 25 May '08

25 May '08

A new version of my raytracer has been posted: http://syn.cs.pdx.edu/~jsnow/glome/ http://hackage.haskell.org/cgi-bin/hackage-scripts/package/glome-hs-0.51 (This should really be named 0.5.1, but I didn't think of that until after I uploaded it to hackage.) There's not much new functionality, but it now uses type classes for the supported primitives, and has been optimized a bit more. Much of the tutorial I hastily wrote for 0.4.x (http://www.haskell.org/haskellwiki/Glome_tutorial) is now quite out of date. Most of the primitives have been moved to their own module, with the exception of SolidItem (an existential type used to make composite primitives), [SolidItem] (allowing me to treat lists of Solids like single solids), Void (a non-object, equivalent to []::[SolidItem]), and Instance (used for transformations). It might be possible to move those to their own modules as well, but it would require mutual recursion between modules, and that's probably more trouble than it's worth. (I made an attempt at that, but I quickly gave up.) I also gave up on trying to use a global mutable variable to count the number of bounding hierarchy nodes a particular ray hits; instead, I added rayint_debug, which behaves just like rayint (the standard ray-object intersection routine), except that it returns an integer (that I can use to count whatever I like) along with the ray intersection. Using a global counter in this instance would have been much simpler, but I don't think I understand "seq" well enough to be able to force the increment to actually happen. http://syn.cs.pdx.edu/~jsnow/glome/Screenshot-glome-hs-bih.png The resulting renders can be very useful to determine where Glome is spending most of its time, and to verify that the the bounding interval hierarchy is really doing the right thing. I also added packet tracing, which makes it possible to trace four rays at a time, using a specialized ray intersection method "packetint". (This is a common technique to amortize the acceleration structure's memory lookup cost over multiple rays.) It seemed to be a big win when I first implemented it before converting over to type classes, but now it seems to be faster without it, so I probably made a mistake somewhere. A cosmetic change is that Glome now renders into a drawlist instead of directly to the screen, so the whole image doesn't get laboriously re-traced whenever there's window damage. Unfortunately, that means you can't watch as it draws anymore, which was a useful way of knowing which parts of the image were slow to render. I've started looking more seriously into optimization (suggestions welcome). Don Stewart's blog post (http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast) was quite useful, but it seems like there's a lot of arcane knowledge required to understand what's really happening in "core" code. Is there any better reference than Andrew Tolmach's paper "An External Representation for the GHC Core Language (2001)" http://citeseer.ist.psu.edu/tolmach01external.html? -jim

2 1

newbie: maintaining relationships
by geoffrey 24 May '08

24 May '08

I am learning haskell and i need some advice about writing functional-style code. Give the following code below, my question is - how do i setup a dependency of User on Common? Obviously what i have there is wrong, because a change in common (i know it's actually immutable) is not reflected in the version captured by User. I understand why my current approach has not a chance a of working, I am using it to, hopefully, illustrate my goal. Thanks for any suggestions > data Common = Common { > cName :: String, > cValue :: Int > } deriving (Show) > data User = User { > uCommon :: Common > } deriving (Show) > makeWorld = (commons, users) > where > commons = [Common "A" 1, Common "B" 2] > users = [User (head commons)] > > main = do > let world = makeWorld > putStrLn (show world)

3 3

strange cabal error
by John Lato 24 May '08

24 May '08

Hello, I recently ran into a strange cabal error. When trying to configure a package (leksah 0.1.1) I get the following error: MacBook-Pro:leksah-0.1.1 jwl$ runhaskell Setup.lhs configure Configuring leksah-0.1.1... Setup.lhs: ghc version >=6.2 is required but the version of /usr/local/bin/ghc could not be determined. MacBook-Pro:leksah-0.1.1 jwl$ /usr/local/bin/ghc --version The Glorious Glasgow Haskell Compilation System, version 6.8.2 This is on Mac OS 10.5.2, with GHC 6.8.2 (installed from Manuel C.'s binary package). Thus far several other packages have built and installed just fine (bytestring, binary, parsec, gtk2hs (from source, not darwinports)). Looking through leksah.cabal and Setup.lhs, I didn't see anything unusual (although I'm far from a cabal expert). I only found one relevant result from google, a Nov. 20th message on cabal-devel about another user getting this message on Debian with ghc 6.8.1. He reported getting this message when running install from a directory without write permissions. It doesn't seem to be a permissions problem for me; I do have write permissions for the directory in which I'm running cabal and all subdirectories. Can anyone tell me what's going on, or give me any advice to try? Would a different version of cabal possibly work? Thanks, John Lato

2 2

Re: [Haskell-cafe] Newbie: State monad example questions
by Olivier Boudry 24 May '08

24 May '08

On Fri, May 23, 2008 at 5:17 PM, Thomas Hartman <tphyahoo(a)gmail.com> wrote: > > Maybe I don't like to read backwards. ;-) > > >>> (from Control.arrow) is like flip (.) > > That's something I considered. I like the `|>` operator found in F# (I hope it's not a curse word on this list) which is equivalent to `flip (.)`. It's easy to define in Haskell (|>) :: (a -> b) -> (b -> c) -> a -> c (|>) = flip (.) I even started to use it in my code and then stopped. It may be a stupid concern but as many optimizations performed by GHC are made through rewrite rules and I was worried that those rules may not fire when using this new operator. I never thought of using `>>>` for this, but again I wonder how it will work with rewrite rules. Olivier.

2 2

Data.Tree.Zipper in the standard libraries
by Krasimir Angelov 24 May '08

24 May '08

Hello Guys, We have Data.Tree in the standard libraries for a long time but for some reason we still don't have standard implementation for Zipper. I wrote recently one implementation for Yi but there are many other versions hanging around. At least I know for some. I propose to add one in the standard libraries i.e. the "containers" package. The version that I use currently is here: http://code.haskell.org/yi/Data/Tree/Zipper.hs If you would like to do code review I will be happy to hear comments. After the API is settled down I will write test cases also. One thing that is worying me is that the current version uses State monad which is in the "mtl" package while the natural place for Data.Tree.Zipper is in "containers". This will create an extra dependency. Is this acceptable? Regards, Krasimir

10 15

gtk2hs linking problems
by Nabil Alsharif 24 May '08

24 May '08

I downloaded the gtk2hs 0.9.12.1 tarball and did the standard configure, make, make install but when I go to compile a test program I get a bunch of errors that look like: compilation IS NOT required [..snip..] (.data+0x38): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziTypes_zdf548_closure' gui.o: In function `r2JC_srt': (.data+0x60): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziButtonsziButton_onClicked_closure' gui.o: In function `r2JC_srt': (.data+0x68): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziTypes_zdf662_closure' gui.o: In function `r2JE_srt': (.data+0x90): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziButtonsziButton_buttonLabel_closure' gui.o: In function `r2JE_srt': (.data+0x98): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziTypes_zdf662_closure' gui.o: In function `r2JG_srt': (.data+0xc0): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziAbstractziContainer_containerChild_closure' gui.o: In function `r2JG_srt': (.data+0xc8): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziTypes_zdf662_closure' gui.o: In function `r2JG_srt': (.data+0xd0): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziTypes_zdf548_closure' gui.o: In function `r2JG_closure': (.data+0x108): undefined reference to `glibzm0zi9zi12zi1_SystemziGlibziAttributes_set_closure' gui.o: In function `r2JG_closure': (.data+0x110): undefined reference to `gtkzm0zi9zi12zi1_GraphicsziUIziGtkziGeneralziGenera This was done on a Ubuntu system. It looks like it can't find a reference to a library but it doesn't say which one. If any one has ran into this problem before or knows what wrong help would be appreciated.

2 1

Re: [Haskell-cafe] Announce: ghc-core, command line pager for reading GHC Core
by Henning Thielemann 23 May '08

23 May '08

On Fri, 23 May 2008, Ketil Malde wrote: > Henning Thielemann <lemming(a)henning-thielemann.de> writes: > >>> An even more advanced tool could show differences between two Core >>> listings [..] >> In this special example, actually simple 'diff' spotted the critical >> difference > > I would suggest Emacs's ediff for this, it lets you refine differing > chunks and highlights the actual differences. If you are an Emacs > user, if not, there are probably other nice diff tools out there.. :-) tkdiff, kompare

1 0