July 2012 - Haskell-Cafe

Reddy on Referential Transparency
by Chris Dornan 31 Jul '12

31 Jul '12

Café, For those who havent seen it Uday Reddy has a comprehensive answer to a request to explain referential transparency on Stack Overflow. http://stackoverflow.com/questions/210835/what-is-referential-transparency/9 859966#9859966 For good measure he finishes with a rather scathing assessment of functional programmers claim to ownership of RT: Functional programmers don't know much of this research. Their ideas on referential transparency are to be taken with a large grain of salt. Marvellous! 'Tis rare to find such a robust assessment combined with understanding (and it certainly makes me think a bit). Have we become a bit complacent about RT? Chris

8 12

Explicit forall - Strange Error
by Shayan Najd Javadipour 31 Jul '12

31 Jul '12

Hi, I wonder why the following code doesn't typecheck in GHC 7.4.1: {-# LANGUAGE GADTs,RankNTypes #-}data T a where T1 :: (forall b. b -> b) -> (forall a. Int -> T a) {- Error: Data constructor `T1' returns type `forall a. Int -> T a' instead of an instance of its parent type `T a' In the definition of data constructor `T1' In the data type declaration for `T' Failed, modules loaded: none. -} While: {-# LANGUAGE GADTs,RankNTypes #-} f :: (forall b. b -> b) -> (forall a. Int -> Maybe a)f = undefined {- ghci> :t f f :: (forall b. b -> b) -> Int -> Maybe a -} Thanks, Shayan

3 3

Detecting numeric overflows
by Евгений Пермяков 31 Jul '12

31 Jul '12

Can someone tell me if there are any primitives, that used to detect machine type overflows, in ghc haskell ? I perfectly understand, that I can build something based on preconditioning of variables, but this will kill any performance, if needed.

4 5

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