- Haskell-Cafe - Haskell.org

ANN: stm-sbchan-0.1 - STM channel with maximum total size of items
by Joey Adams 31 Jul '12

31 Jul '12

This package provides a bounded channel type for STM. TBChan (in stm-chans) and TBQueue (introduced in stm 2.4) are bounded channels that limit the number of items in the channel. SBChan, on the other hand, limits the total size of items in the channel, where "size" is defined by providing an instance of the ItemSize class: data Entry = Entry Int64 ByteString Time -- | Estimated amount of memory an 'Entry' requires, -- including channel overhead instance ItemSize Entry where itemSize (Entry _ s _) = B.length s + 200 Then, "SBChan Entry" is a channel that limits (approximately) the amount of memory the entries take up. SBChan can also be used as a regular count-bounded channel by using the SBCItem newtype wrapper, where itemSize is always 1. http://hackage.haskell.org/package/stm-sbchan Enjoy! -Joey --- Implementation details --- itemSize returns an Int. I originally considered using an associated type, so users could pick their own number type to use. However, this would have made the implementation harder to reason about, if we had to worry about the user picking an ill-behaved number type like Float. Besides, Int is usually adequate for representing in-memory sizes. This library takes a lot of ideas from TChan and TBChan. I decided to use the linked list of TVars approach that TChan uses, rather than the pair of lists approach T(B)Queue uses, to avoid a potential problem with code like this: msg <- readTBQueue case msg of Foo -> ... Bar -> ... If the transaction is repeated a lot due to retries or invalidation, and readTBQueue needs to turn around the list at this point, then we'll end up repeating O(n) work a bunch of times. SBChan uses stm-tlist, a library I wrote that is based on TChan's internal representation. Also, SBChan uses the usual trick for reducing reader-writer contention by having two counters for capacity, one for readers and one for writers.

1 0

What does unpacking an MVar really mean?
by Leon Smith 31 Jul '12

31 Jul '12

I admit I don't know exactly how MVars are implemented, but given that they can be aliased and have indefinite extent, I would think that they look something vaguely like a cdatatype ** var, basically a pointer to an MVar (which is itself a pointer, modulo some other things such as a thread queue.) And, I would think that "unpacking" such an structure would basically be eliminating one layer of indirection, so it would then look vague like a cdatatype * var. But again, given aliasing and indefinite extent, this would seem to be a difficult thing to do. Actually this isn't too difficult if an MVar only exists in a single unpacked structure: other references to the MVar can simply be pointers into the structure. But the case where an MVar is unpacked into two different structures suggests that, at least in some cases, an "unpacked" MVar is still a cdatatype ** var; So, is my understanding more or less correct? Does anybody have a good, succinct explanation of how MVars are implemented, and how they are unpacked? One final question, assuming that unpacking an MVar really does eliminate a layer of indirection, and that other references to that MVar are simply pointers into a larger structure, what happens to that larger structure when there are no more references to it (but still some references to the MVar?) Given the complications that must arise out of a doubly "unpacked" MVar, I'm going to guess that the larger structure does get garbage collected in this case, and that the MVar becomes dislodged from this structure. Would that MVar then be placed directly inside another unpacked reference, if one is available? Best, Leon

3 4

IMAGE_FILE_LARGE_ADDRESS_AWARE (4GB on Win64) ... any best practices??
by Nick Rudnick 31 Jul '12

31 Jul '12

Dear Haskellers, did anybody of you stumble about surprisingly having a 2GB memory limit on Win64? I admit I didn't get it at once (just about to finish a complete memcheck... ;-) -- but of course there already is a discussion of this: http://stackoverflow.com/questions/10743041/making-use-of-all-available-ram… Unfortunately, this left me a little stupid about how to actually get a program running with IMAGE_FILE_LARGE_ADDRESS_AWARE -- did anybody try this successfully (or even not...) and has experience to share? Usually a Linuxer, I am just about to begin exploring the possibilities of Haskell on Windows, please forgive. Thanks a lot advance, Nick

1 0

How to define a Monad instance
by Thiago Negri 31 Jul '12

31 Jul '12

Hello. I'm trying to understand Monads. In order to do so, I decided to create my own Monad for a simple domain-specific language. The idea is to define a way to describe a multi-value replacement inside do-notation. Example of a function doing what I want (without Monads): replaceAll :: (a -> Maybe a) -> [a] -> [a] replaceAll f xs = go f xs [] where go :: (a -> Maybe a) -> [a] -> [a] -> [a] go _ [] acc = acc go f (x:xs) acc = let acc' = acc ++ [fromMaybe x (f x)] in acc' `seq` go f xs acc' Example of a replacement table: table :: Char -> Maybe Char table x = case x of 'a' -> Just 'b' 'A' -> Just 'B' _ -> Nothing Example of use: \> replaceAll table "All I want" "Bll I wbnt" Now, want I tried to do... As Monads are used for sequencing, first thing I did was to define the following data type: data TableDefinition a = Match a a (TableDefinition a) | Restart So, to create a replacement table: table' :: TableDefinition Char table' = Match 'a' 'b' (Match 'A' 'B' Restart) It look like a Monad (for me), as I can sequence any number of replacement values: table'' :: TableDefinition Char table'' = Match 'a' 'c' (Match 'c' 'a' (Match 'b' 'e' (Match 'e' 'b' Restart))) In order to run the replacement over a list, I've defined the following function: runTable :: Eq a => TableDefinition a -> [a] -> [a] runTable t = go t t [] where go _ _ acc [] = acc go s Restart acc (x:xs) = let acc' = (acc ++ [x]) in acc' `seq` go s s acc' xs go s (Match a b m) acc ci@(x:xs) | x == a = let acc' = (acc ++ [b]) in acc' `seq` go s m acc' xs | otherwise = go s m acc ci The result is still the same: \> runTable table' "All I want" "Bll I wbnt" I'd like to define the same data structure as: newTable :: TableDefinition Char newTable = do 'a' :> 'b' 'A' :> 'B' But I can't figure a way to define a Monad instance for that. :( Can you help me? Thanks, Thiago.

4 5

Relational Algebra library: first version on GitHub
by Paul Visschers 30 Jul '12

30 Jul '12

Hello, A couple of weeks ago I asked if there was interest in a library that implements a type-safe relational algebra. The response was positive, so I have spruced up the code I had a bit and created a repository on GitHub at: https://github.com/PaulVisschers/relational-algebra It is a very rudimentary version. The code is not documented and there is only a very basic example database in Test.hs. It might be helpful to look at HaskellDB's PrimQuery and PrimExpr, as this library is mostly a direct copy from that (but typed). I will add some decent examples of expressions and queries shortly. If you check it out, please comment on it and let me know if you want to contribute. Since this is going to be my first release, any feedback is welcome. Paul Visschers

5 6

CRIP: the Curiously Reoccuring Instance Pattern
by Ryan Ingram 30 Jul '12

30 Jul '12

With apologies to Jim Coplien :) I've been seeing this pattern in a surprising number of instance definitions lately: instance (a ~ ar, b ~ br) => Mcomp a ar b br [1] instance (b ~ c, CanFilterFunc b a) => CanFilter (b -> c) a [2] The trick is that since instance selection is done entirely on the instance head, these instances are strictly more general than the ones they replace: instance Mcomp a a b b instance CanFilterFunc b => CanFilter (b -> b) a The compiler has to do a lot more work to select these instances; it has to prove that the matching types actually match before it can select the instance; if it can't, it won't select an instance, and instead will complain about no instance "CLASS Int a". But with the CRIP, you help the compiler--it chooses the general instance, and then gets a constraint to solve. The constraint forces the two types to unify, or else there is a type error. What I'm wondering is--are there many cases where you really want the non-constraint-generating behavior? It seems like (aside from contrived, ahem, instances) whenever you have instance CLASS A B where A and B share some type variables, that there aren't any valid instances of the same class where they don't share the types in that way. For example, I've never really seen a class in practice with instances like class Foo a b instance Foo a a instance Foo ConcreteTypeA ConcreteTypeB Note that it's very difficult to use polymorphic types in the second instance without risking overlap. TL;DR: I, for one, welcome our new type equality constraint overlords. -- ryan [1] http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/99611 [2] http://www.yesodweb.com/blog/2012/07/classy-prelude

1 0

Polyvariadic composition
by Artyom Kazak 30 Jul '12

30 Jul '12

Hello, I have accidentally written my version of polyvariadic composition combinator, `mcomp`. It differs from Oleg’s version ( http://okmij.org/ftp/Haskell/polyvariadic.html#polyvar-comp ) in three aspects: a) it is simpler, b) it works without enumerating basic cases (all existing types, in other words), and c) it needs more type extensions. > {-# LANGUAGE > MultiParamTypeClasses > , FunctionalDependencies > , FlexibleInstances > , UndecidableInstances > , TypeFamilies , OverlappingInstances > #-} > > class Mcomp a ar b br | a br -> b where > mcomp :: a -> (ar -> br) -> b > > instance (a ~ ar, b ~ br) => Mcomp a ar b br where > mcomp a f = f a > > instance (Mcomp a ar b br) => Mcomp (x -> a) ar (x -> b) br where > mcomp a f = \x -> mcomp (a x) f My question is: why doesn’t it work when I replace instance (a ~ ar, b ~ br) => Mcomp a ar b br with instance Mcomp a a b b ? I thought that equal letters mean equal types…

3 2

why does a foldr not have a space leak effect?
by Qi Qi 30 Jul '12

30 Jul '12

Hi, I wonder why a foldr does not have a space leak effect? Any hints? Thanks. Qi

5 8

AI - machine learning
by miro 30 Jul '12

30 Jul '12

Hi All, recently I started to take a look at haskell, especially at AI. I can see some email addresses of interested people there but not so much of other activity behind. Does it exist some mailing group especially for AI? Basically I'm interested in trying some machine learning algorithms. Start with reinforcement learning and value-based), and go towards AGI (Artificial General Intelligence). Does anybody know about some already existing haskell approaches, or is there anybody working on this? Cheers, m.

4 3

Logging pure code
by Marco Túlio Gontijo e Silva 30 Jul '12

30 Jul '12

Hi. I'm using the hslogger library for logging pure code, using the following function: uLog :: Priority -> String -> a -> a uLog pri str x = unsafePerformIO $ logM rootLoggerName pri str >> return x Everything was working fine, till I used uLog on a very accessed function. Then the program started to fail with: thread blocked indefinitely in an MVar operation I've changed uLog to: uLog :: Priority -> String -> a -> a uLog pri str x = unsafePerformIO $ hPutStrLn stderr (show str) >> return x And I noticed on the log that two messages were sent "at the same time" on the point where the version with hslogger fails: "canonicate 4 "canonicate 1 \r\n\t\t\t\t\t\t\t\tRio Branco = rio branco" "canonicate 2 AC\r\n\t\t\t\t\t\t\t\t = ac" ac = ac" They were sent as (in any order): "canonicate 4 ac = ac" "canonicate 1 \r\n\t\t\t\t\t\t\t\tRio Branco = rio branco" "canonicate 2 AC\r\n\t\t\t\t\t\t\t\t = ac" I tried changing hslogger to avoid calling modifyMVar when getting logger for rootLoggerName, and using withMVar instead, but the problem persisted. I tried to create a simple test case to reproduce the problem, but I couldn't, all test cases I created worked as expected. As I was with no other ideas, I tried some things that make little sense. This happens with optimization or without it. Following http://hackage.haskell.org/trac/ghc/ticket/5859 I tried using -fno-state-hack, but the problem persisted. I tried adding NOINLINE to uLog, without success. I also tried changing unsafePerformIO to unsafeDupablePerformIO. I thought that the only thing I needed to take care while using unsafePerformIO was knowing that the time of execution is undetermined and that it could even run more than once. This is not a problem for my logging. Is there something else I should be aware while using unsafePerformIO? Greetings. -- marcot http://marcot.eti.br/

4 4