May 2010 - Haskell-Cafe

Multidimensional generalization of the vector package
by Gregory Crosswhite 27 May '10

27 May '10

Hey everyone, I have been thinking about how to generalize the vector package to multiple dimensions, and I'd like to share my ideas with you all in the hope of having people smarter than me share their thoughts on how it could be improved --- *especially* regarding how to make it efficient! The standard way to represent a memory layout is to use a stride vector --- i.e., a vector which lets you get the (flat) index in memory of a given element by dotting the stride vector with the multidimensional index vector. This has the advantage that one can efficiently manipulate it to represent views with arbitrary slices, subranges, subranges plus striping (i.e., take every k-th element), and transpositions. Basically the only thing it can't do is represent a weird view where we, say, take every index along a particular dimension that is a prime number. Having said this, it might be useful to abstract the memory layout in order to preserve generality. Thus, I was thinking that the layout of the multidimensional vector could be represented as a type class with an associated type family: class MemoryLayout layout where type LayoutIndex layout :: * indexOf :: layout -> (LayoutIndex layout) -> Int firstIndex :: layout -> (LayoutIndex layout) -> Int lastIndex :: layout -> (LayoutIndex layout) -> Int withinBounds :: layout -> (LayoutIndex layout) -> Bool ... etc. It is important that we be able to iterate through the array efficiently. One way that this could be done is through the use of cursors. class MemoryLayout layout where ... type LayoutCursor layout :: * ... getCursorAt :: layout -> (LayoutIndex layout) -> (LayoutCursor cursor) getFirstCursor :: layout -> (LayoutCursor cursor) getLastCursor :: layout -> (LayoutCursor cursor) indexOfCursor :: layout -> (LayoutCursor cursor) -> Int advanceCursor :: layout -> (LayoutCursor cursor) -> (LayoutCursor cursor) In general these unfortunately cannot be integers because integers don't contain enough information to tell us about where we need to go next inside a non-contiguous array. The alternative is to use a data structure, but then we may potentially have lots of potentially wasteful allocations, deallocations, and copying going on unless we can somehow cause the cursor to be updated destructively. Fortunately, much of the time our array will be contiguous, so we can have a special case fast-path for this case: class MemoryLayout layout where ... layoutIsContiguous :: layout -> Bool layoutIsContiguousWhenTraversedInRowMajorOrder :: layout -> Bool layoutIsContiguousWhenTraversedInColumnMajorOrder :: layout -> Bool Then we know that we can just iterate through the array in the order of the indices. It turns out that it is not hard to compute whether a layout is contiguous efficiently. For example, in the code that implements cuts and slicing we can actually check to see if the new view is still contiguous and simply cache this in the layout. For restricted cases of layouts (when there aren't transpositions) it isn't too hard to just scan through the layout and see if it is contiguous. Another way to iterate through the array is to provide this capability by constructing functions that traverse through the array for us and call some user-supplied function on each element. This actually can be a lot more efficient (since by using recursive algorithms it can store the information that it needs on the stack rather than using heap allocations) but it is much more restrictive, and it requires special cases for traversing multiple arrays in parallel. Probably the most general way to sum/fold/etc. over particular dimensions (i.e., given a 4D vector, sum over the first and third dimensions leaving the second and fourth dimensions) is simply to generalize the notion of cursors, so that rather than iterating over elements we are iterating over views of the array. class (MemoryLayout layout1, MemoryLayout layout2) => MemoryLayoutSubviewable layout1 layout2 where type MemoryLayoutViewSetSlicer layout1 layout2 :: * type MemoryLayoutViewSet layout1 layout2 :: * getViewSet :: (MemoryLayoutViewSetSlicer layout1 layout2) -> layout1 -> (MemoryLayoutViewSet layout1 layout2) advanceViewSet :: (MemoryLayoutViewSet layout1 layout2) -> (MemoryLayoutViewSet layout1 layout2) currentView :: MemoryLayoutViewSet layout1 layout2 -> layout2 This way we can hand getViewSet some "slicer" that selects some dimensions to be reduced but not others and get back a set of views that we can iterate over, providing a generalization of the sum and fold functionality provided by repa. Although these framework allows us to stay general, in practice working with shapes that are fixed-length vectors (I personally would prefer the Vec package over the hand-rolled one in repa) tends to be easiest, because it allows one to write recursive algorithms employing type families that can define views for arrays with arbitrary dimensions. Also, in practice one can construct type aliases any helper functions such as i1 a = a :. () i2 a b = a :. b :. () i3 a b c = a:. b:. c:. () . . . type I0 = () type I1 = Int : I0 type I2 = Int :. I1 . . . etc. so that we construct values via (i2 x y) rather than (x :. y :. ()). Any thoughts? Cheers, Greg

1 0

Unicode vs. System.Directory
by Arie Peterson 27 May '10

27 May '10

After upgrading to haskell-platform-2010.1.0.0, with the improved unicode support for IO in ghc-6.12, I hoped to be able to deal with filenames containing non-ascii characters. This still seems problematic, though: $ ls m×n♯α $ ghci GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Prelude> :m +System.Directory Prelude System.Directory> getDirectoryContents "." >>= mapM_ putStrLn .. mÃnâ¯Î± . I hope this passes through the various email systems unharmed; on my terminal, the output of 'ls' contains shiny unicode characters, while 'ghci' garbles up the filename. (My locale is en_GB.utf8.) Similar problems arise with functions such as 'copyFile', which refuses to handle filenames with non-ascii characters (unless wrapping it with encoding functions). Is this a known problem? I searched ghc's trac, but there are no relevant bugs for the component 'libraries/directory'. I have parts of a unicode-aware layer on top of System.Directory laying around somewhere. I was rather hoping to ditch it, but I can polish it and put it on hackage, if people are interested. Kind regards, Arie

5 4

double2Float is faster than (fromRational . toRational)
by Daniel van den Eijkel 27 May '10

27 May '10

Dear Haskellers, I just want to share an observation. I had to convert a Double to a Float value in an inner loop of an application, and I used somethin like this: xf = (fromRational $ toRational xd) :: Float The program works on windows but it did not on OSX - it was too slow. Now, after big headaches and much frustration, I replaced the code above with this line (why didn't I come up with this earlier?): xf = double2Float xd and now everything works just fine. I am not really surprised by the speed-up (and no-one should be), but I am still surprised how often such kinds of unobvious problems occur while programming in Haskell. So I write this email just to remind me and you to look out for such pitfalls. Best, Daniel

7 8

Re: [Gtk2hs-users] Problem when installing gtk2hs.
by Magicloud Magiclouds 27 May '10

27 May '10

I only have one alex installed under ~/.cabal/bin. It seems working with shell environment, but not cabal. On Thu, May 27, 2010 at 1:40 PM, Axel Simon <Axel.Simon(a)in.tum.de> wrote: > Hi Magicloud, > > On May 27, 2010, at 4:11, Magicloud Magiclouds wrote: > >> Hi, I have met similar problem before, and I do not know what to do. >> >> # cabal install --reinstall gtk2hs-buildtools >> Resolving dependencies... >> Configuring gtk2hs-buildtools-0.9... >> cabal: alex is required but it could not be found. >> cabal: Error: some packages failed to install: >> gtk2hs-buildtools-0.9 failed during the configure step. The exception was: >> ExitFailure 1 >> # alex -v >> Alex version 2.3.3, (c) 2003 Chris Dornan and Simon Marlow > > I don't think this is due to us. Are there perhaps other alex installations > on your path? Or in ~/.cabal/bin? > > Axel > > >> -- >> 竹密岂妨流水过 >> 山高哪阻野云飞 >> >> >> ------------------------------------------------------------------------------ >> >> _______________________________________________ >> Gtk2hs-users mailing list >> Gtk2hs-users(a)lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/gtk2hs-users > > -- 竹密岂妨流水过山高哪阻野云飞

4 4

Problem when installing gtk2hs.
by Magicloud Magiclouds 26 May '10

26 May '10

Hi, I have met similar problem before, and I do not know what to do. # cabal install --reinstall gtk2hs-buildtools Resolving dependencies... Configuring gtk2hs-buildtools-0.9... cabal: alex is required but it could not be found. cabal: Error: some packages failed to install: gtk2hs-buildtools-0.9 failed during the configure step. The exception was: ExitFailure 1 # alex -v Alex version 2.3.3, (c) 2003 Chris Dornan and Simon Marlow -- 竹密岂妨流水过山高哪阻野云飞

1 0

Re: [Haskell-cafe] [reactive] A pong and integrate
by Patai Gergely 26 May '10

26 May '10

> I did not look thoroughly at elerea, but at least, when I tried its sample > "dungeons of wor" it worked properly ;) Elerea has its own 'beauty' though. I suggest unpacking the source of dow and executing it in ghci, the problem will be obvious as you play at length. Unfortunately, Elerea doesn't really work well as an EDSL, however much I'd like it to. Its main issue is that unreferenced entities keep using CPU time until they are garbage collected -- this comes from the necessity to keep them referentially transparent, i.e. behaving the same way regardless of how they are observed --, and currently I don't see any way to solve that without implementing a dedicated runtime for dynamic stream processing. So there, no FRP library without a catch for you. ;) Gergely -- http://www.fastmail.fm - A fast, anti-spam email service.

9 30

MultiParamClasses question
by Eugeny N Dzhurinsky 26 May '10

26 May '10

Hello, all! I'm trying to create set of polymorphic functions for working with custom containers. I decided to try out typeclass and define generic function, which uses the methods from the typeclass. The quick and naive solution is listed below: ================================================================================ {-# OPTIONS_GHC -XMultiParamTypeClasses -XTypeSynonymInstances #-} import Data.List as L class Storage k t a b where stExists :: k -> t -> b -> Bool stAdjust :: k -> t -> ( a -> a ) -> b -> b stInsert :: k -> t -> a -> b -> b stList :: b -> [a] type IxPair k t = ( k, t, String, String) data Pair = Pair { name, value :: String } type IxPairParser k t = Pair -> Maybe (IxPair k t) type RecordUpdateF r = String -> String -> r -> r convertPairsToRecords :: (Storage k t a b) => b -> RecordUpdateF a -> IxPairParser k t -> a -> [Pair] -> [a] convertPairsToRecords storg updateRecF parsePairF initRec = stList . processWithPairs where processWithPairs = foldl' ( (. parsePairF) . updateStorage ) storg updateStorage st Nothing = st updateStorage st ( Just (idx, sType, name, value) ) | stExists idx sType st = stAdjust idx sType (updateRecF name value) st | otherwise = stInsert idx sType (updateRecF name value initRec) st ================================================================================ so I want to provide methods for checking if a record with given key exists, update a record, insert a record and get list of records. Sounds similar as for Map, but I want also to be able to operate on map of maps, or lists, or whatever. I don't really see any problem with the code above, however GHC 6.12.1 does think that I am doing something weird. And it gives me this error log: ================================================================================ test.hs:19:60: Could not deduce (Storage k t a1 b) from the context (Storage k1 t1 a1 b) arising from a use of `stList' at test.hs:19:60-65 Possible fix: add (Storage k t a1 b) to the context of the type signature for `convertPairsToRecords' In the first argument of `(.)', namely `stList' In the expression: stList . processWithPairs In the definition of `convertPairsToRecords': convertPairsToRecords storg updateRecF parsePairF initRec = stList . processWithPairs where processWithPairs = foldl' ((. parsePairF) . updateStorage) storg updateStorage st Nothing = st updateStorage st (Just (idx, sType, name, value)) | stExists idx sType st = stAdjust idx sType (updateRecF name value) st | otherwise = stInsert idx sType (updateRecF name value initRec) st test.hs:21:53: Could not deduce (Storage k1 t1 a b) from the context (Storage k1 t1 a1 b) arising from a use of `updateStorage' at test.hs:21:53-65 Possible fix: add (Storage k1 t1 a b) to the context of the type signature for `convertPairsToRecords' In the second argument of `(.)', namely `updateStorage' In the first argument of `foldl'', namely `((. parsePairF) . updateStorage)' In the expression: foldl' ((. parsePairF) . updateStorage) storg ================================================================================ Can somebody please advice, what am I doing in wrong way? Thank you all in advance! -- Eugene Dzhurinsky

4 6

Declaring a tuple of instances of Enums as an instance of the Enum class
by R J 25 May '10

25 May '10

Say I've got a type "Month" declared as an instance of the "Enum" class, and a type "MonthPair" declared as a pair of months: data Month = January | February | March | April | May | June | July | August | September | October | November | December deriving (Eq, Enum, Ord, Show) type MonthPair = (Month, Month) deriving (Enum) The "deriving" on "MonthPair" gives me the error "parse error on input 'deriving'". Why is this error generated? Is there a syntax error, or is there a conceptual problem with enumerating a Cartesian product, such as Month x Month? The cardinality of the Cartesian product is finite (including the bottom values, cardinality = 1 + (12 + 1)*(12 + 1) = 170), and so the product is amenable at least to some arbitrary enumeration (such as Cantor's diagonal method). Thanks. _________________________________________________________________ The New Busy think 9 to 5 is a cute idea. Combine multiple calendars with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multicalendar&ocid=PID2…

5 5

Re: [Haskell-cafe] [ANNOUNCE] SyntaxMacros-0.1
by Oscar Finnsson 25 May '10

25 May '10

> We are pleased to announce the first release of SyntaxMacros [1]. Very interesting. This is something I've been interested in since I first heard of Ziggurat. In which order do you recommend I try to learn the packages: HList -> AspectAG -> SyntaxMacros? I tried to read the SyntaxMacros-paper but had a hard time understanding which parts belonged to the package and which parts belonged to your new mini-language. Do you got the mini-language as a separate download? You mention in the paper that the source of the paper is in literate Haskell and that the code is available but I can't find it at the wiki. I found some code (Expr.hs, Main.hs) in the examples-folder in the packages source code (SyntaxMacrox-0.1.tar.gz) but it doesn't seem to match 1:1 to the code in the paper (couldn't for example find extSpecChars in the paper or updateFinalEnv in the source code). -- Oscar

2 1

Re: Cabal sqlite3 installation problems
by Ben 25 May '10

25 May '10

i have this exact problem, on linux x86_64, as well. b Hok Shun Poon fushunpoon at googlemail.com Sun May 23 19:51:20 EDT 2010 Previous message: memory useage of data types in the time package Next message: Text.Regex library with bytestrings? Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Hello, This is a question about how cabal-install finds 'installed foreign libraries' when trying to satisfy dependencies for packages like hdbc-sqlite3 on Windows. Sadly, the current setup means that I must use Windows 7 to develop code. I've already followed steps on http://wiki.github.com/jgoerzen/hdbc/frequentlyaskedquestions to place the .dll and the .h files in the correct places; it's just that cabal never seems to find it, despite being given --extra-lib-dirs= and --extra-include-dirs= directives. The message is as follows: > cabal install hdbc-sqlite3 --extra-lib-dirs=D:\dev\libs\database\sqlite Resolving dependencies... Configuring HDBC-sqlite3-2.3.0.0... cabal: Missing dependency on a foreign library: * Missing C library: sqlite3 This problem can usually be solved by installing the system package that provides this library (you may need the "-dev" version). If the library is already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where it is. cabal: Error: some packages failed to install: HDBC-sqlite3-2.3.0.0 failed during the configure step. The exception was: ExitFailure 1 The strangest thing is, I've successfully made cabal build this package before (with a different version of Haskell Platform)... what's going on? I'm using cabal-install version 0.8.2 and Cabal library version 1.8.0.2. Hok

2 1