February 2010 - Haskell-Cafe

ANNOUNCE: vty-ui 0.3
by Jonathan Daugherty 19 Feb '10

19 Feb '10

I'm happy to announce the release of vty-ui 0.3. Get it from Hackage: http://hackage.haskell.org/package/vty-ui Or get the source with darcs: http://repos.codevine.org/vty-ui Project homepage: http://codevine.org/vty-ui/ This version of vty-ui features a richer rendering engine, generalized text transformations, and a more functional style. If you've written any applications to use vty-ui, your type signatures and usage of a few of the built-in widget types will need to change but the API is largely the same. In particular, the largest change was a refactoring inspired by Luke Palmer's blog post, "Haskell Antipattern: Existential Typeclass," which targeted vty-ui (among other libraries) in its treatment of the topic: http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-… Here's a summary of changes: General * Replace Widget type class with a concrete Widget type * Move text widget into Graphics.Vty.Widgets.Text * Add support for generalized text "formatters" * Replace WrappedText widget type with a text-wrapping formatter * Provide a regex-based text-highlighting formatter (see the demo for an example) * Refactor the rendering engine to provide "address" information so you can get coordinates and size for rendered widgets * Add a few QuickCheck tests (and related fixes) Enjoy! -- Jonathan Daugherty

1 0

Implementing "unionAll"
by Leon Smith 18 Feb '10

18 Feb '10

With the urging and assistance of Omar Antolín Camarena, I will be adding two functions to data-ordlist: mergeAll and unionAll, which merge (or union) a potentially infinite list of potentially infinite ordered lists, under the assumption that the heads of the non-empty lists appear in a non-decreasing sequence. Union takes two sorted lists and produces a new sorted list; an element occurs in the result as many times as the maximum number of occurrences in either list. The unionAll function generalizes this behavior to an infinite number of lists. A reasonable implementation of mergeAll is: > import Data.List.Ordered(merge, union) > mergeAll :: Ord a => [[a]] -> [a] > mergeAll = foldr (\(x:xs) ys -> x : merge xs ys) [] However, for many inputs, we can do better; the library implementation of mergeAll is based on H. Apfelmus's article "Implicit Heaps", which presents a simplification of Dave Bayer's "venturi" algorithm. The difference is that the foldr version uses a line of comparisons, whereas "venturi" uses a tree of comparisons. http://apfelmus.nfshost.com/articles/implicit-heaps.html http://www.mail-archive.com/haskell-cafe@haskell.org/msg27612.html However, as Omar pointed out to me, the following implementation of unionAll has a flaw: > unionAll :: Ord a => [[a]] -> [a] > unionAll = foldr (\(x:xs) ys -> x : union xs ys) [] Namely unionAll [[1,2],[1,2]] should return [1,2], whereas it actually returns [1,1,2]. After some work, I believe I have generalized H. Apfelmus's algorithm to handle this; however it seems a bit complicated. I would love feedback, especially with regard to simplifications, bugs, testing strategies, and optimizations: > unionAll' :: Ord a => [[a]] -> [a] > unionAll' = unionAllBy compare > data People a = VIP a (People a) | Crowd [a] > unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a] > unionAllBy cmp xss = loop [ (VIP x (Crowd xs)) | (x:xs) <- xss ] > where > loop [] = [] > loop ( VIP x xs : VIP y ys : xss ) > = case cmp x y of > LT -> x : loop ( xs : VIP y ys : xss ) > EQ -> loop ( VIP x (union' xs ys) : unionPairs xss ) > GT -> error "Data.List.Ordered.unionAll: assumption violated!" > loop ( VIP x xs : xss ) > = x : loop (xs:xss) > loop [Crowd xs] = xs > loop (xs:xss) = loop (unionPairs (xs:xss)) > > unionPairs [] = [] > unionPairs [x] = [x] > unionPairs (x:y:zs) = union' x y : unionPairs zs > > union' (VIP x xs) (VIP y ys) > = case cmp x y of > LT -> VIP x (union' xs (VIP y ys)) > EQ -> VIP x (union' xs ys) > GT -> error "Data.List.Ordered.unionAll: assumption violated!" > union' (VIP x xs) (Crowd ys) = VIP x (union' xs (Crowd ys)) > union' (Crowd []) ys = ys > union' (Crowd xs) (Crowd ys) = Crowd (unionBy cmp xs ys) > union' xs@(Crowd (x:xt)) ys@(VIP y yt) > = case cmp x y of > LT -> VIP x (union' (Crowd xt) ys) > EQ -> VIP x (union' (Crowd xt) yt) > GT -> VIP y (union' xs yt) -- Leon

6 16

Re: [Haskell-cafe] Category Theory woes
by Michael Matsko 18 Feb '10

18 Feb '10

Nick, Actually, clopen is a set that is both closed and open. Not one that is neither. Except in the case of half-open intervals, I can't remember talking much in topology about sets with a partial boundary. Category theory-wise. No one seems to have mentioned MacLane's "Categories for the Working Mathematician." Although, I don't seem to recall instant enlightenment when I picked it up. Mike ----- Original Message ----- From: "Nick Rudnick" <joerg.rudnick(a)t-online.de> To: "Michael Matsko" <msmatsko(a)comcast.net> Cc: haskell-cafe(a)haskell.org Sent: Thursday, February 18, 2010 4:54:03 PM GMT -05:00 US/Canada Eastern Subject: Re: [Haskell-cafe] Category Theory woes Hi Mike, of course... But in the same spirit, one could introduce a straightforward extension, «partially bordered», which would be as least as good as «clopen»... ;-) I must admit we've come a little off the topic -- how to introduce to category theory. The intent was to present some examples that mathematical terminology culture is not that exemplary as one should expect, but to motivate an open discussion about how one might «rename refactor» category theory (of 2:48 PM). I would be very interested in other people's proposals... :-) Michael Matsko wrote: Nick, That is correct. An open set contains no point on its boundary. A closed set contains its boundary, i.e. for a closed set c, Closure(c) = c. Note that for a general set, which is neither closed or open (say the half closed interval (0,1]), may contain points on its boundary. Every set contains its interior, which is the part of the set without its boundary and is contained in its closure - for a given set x, Interior(x) is a subset of x is a subset of Closure(x). Mike ----- Original Message ----- From: "Nick Rudnick" <joerg.rudnick(a)t-online.de> To: "Michael Matsko" <msmatsko(a)comcast.net> Cc: haskell-cafe(a)haskell.org Sent: Thursday, February 18, 2010 3:15:49 PM GMT -05:00 US/Canada Eastern Subject: Re: Fwd: [Haskell-cafe] Category Theory woes Hi Mike, so an open set does not contain elements constituting a border/boundary of it, does it? But a closed set does, doesn't it? Cheers, Nick Michael Matsko wrote: ----- Forwarded Message ----- From: "Michael Matsko" <msmatsko(a)comcast.net> To: "Nick Rudnick" <joerg.rudnick(a)t-online.de> Sent: Thursday, February 18, 2010 2:16:18 PM GMT -05:00 US/Canada Eastern Subject: Re: [Haskell-cafe] Category Theory woes Gregg, Topologically speaking, the border of an open set is called the boundary of the set. The boundary is defined as the closure of the set minus the set itself. As an example consider the open interval (0,1) on the real line. The closure of the set is [0,1], the closed interval on 0, 1. The boundary would be the points 0 and 1. Mike Matsko ----- Original Message ----- From: "Nick Rudnick" <joerg.rudnick(a)t-online.de> To: "Gregg Reynolds" <dev(a)mobileink.com> Cc: "Haskell Café List" <haskell-cafe(a)haskell.org> Sent: Thursday, February 18, 2010 1:55:31 PM GMT -05:00 US/Canada Eastern Subject: Re: [Haskell-cafe] Category Theory woes Gregg Reynolds wrote: On Thu, Feb 18, 2010 at 7:48 AM, Nick Rudnick < joerg.rudnick(a)t-online.de > wrote: IM(H??)O, a really introductive book on category theory still is to be written -- if category theory is really that fundamental (what I believe, due to its lifting of restrictions usually implicit at 'orthodox maths'), than it should find a reflection in our every day's common sense, shouldn't it? Goldblatt works for me. Accidentially, I have Goldblatt here, although I didn't read it before -- you agree with me it's far away from every day's common sense, even for a hobby coder?? I mean, this is not «Head first categories», is it? ;-)) With «every day's common sense» I did not mean «a mathematician's every day's common sense», but that of, e.g., a housewife or a child... But I have became curious now for Goldblatt... * the definition of open/closed sets in topology with the boundary elements of a closed set to considerable extent regardable as facing to an «outside» (so that reversing these terms could even appear more intuitive, or «bordered» instead of closed and «unbordered» instead of open), Both have a border, just in different places. Which elements form the border of an open set?? As an example, let's play a little: Arrows: Arrows are more fundamental than objects, in fact, categories may be defined with arrows only. Although I like the term arrow (more than 'morphism'), I intuitively would find the term «reference» less contradictive with the actual intention, as this term Arrows don't refer. A *referrer* (object) refers to a *referee* (object) by a *reference* (arrow). Categories: In every day's language, a category is a completely different thing, without the least Not necesssarily (for Kantians, Aristoteleans?) Are you sure...?? See http://en.wikipedia.org/wiki/Categories_(Aristotle) ... If memory serves, MacLane says somewhere that he and Eilenberg picked the term "category" as an explicit play on the same term in philosophy. In general I find mathematical terminology well-chosen and revealing, if one takes the trouble to do a little digging. If you want to know what terminological chaos really looks like try linguistics. ;-) For linguistics, granted... In regard of «a little digging», don't you think terminology work takes a great share, especially at interdisciplinary efforts? Wouldn't it be great to be able to drop, say 20% or even more, of such efforts and be able to progress more fluidly ? -g _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Fwd: [Haskell-cafe] Category Theory woes
by Michael Matsko 18 Feb '10

18 Feb '10

----- Forwarded Message ----- From: "Michael Matsko" <msmatsko(a)comcast.net> To: "Nick Rudnick" <joerg.rudnick(a)t-online.de> Sent: Thursday, February 18, 2010 2:16:18 PM GMT -05:00 US/Canada Eastern Subject: Re: [Haskell-cafe] Category Theory woes Gregg, Topologically speaking, the border of an open set is called the boundary of the set. The boundary is defined as the closure of the set minus the set itself. As an example consider the open interval (0,1) on the real line. The closure of the set is [0,1], the closed interval on 0, 1. The boundary would be the points 0 and 1. Mike Matsko ----- Original Message ----- From: "Nick Rudnick" <joerg.rudnick(a)t-online.de> To: "Gregg Reynolds" <dev(a)mobileink.com> Cc: "Haskell Café List" <haskell-cafe(a)haskell.org> Sent: Thursday, February 18, 2010 1:55:31 PM GMT -05:00 US/Canada Eastern Subject: Re: [Haskell-cafe] Category Theory woes Gregg Reynolds wrote: On Thu, Feb 18, 2010 at 7:48 AM, Nick Rudnick < joerg.rudnick(a)t-online.de > wrote: IM(H??)O, a really introductive book on category theory still is to be written -- if category theory is really that fundamental (what I believe, due to its lifting of restrictions usually implicit at 'orthodox maths'), than it should find a reflection in our every day's common sense, shouldn't it? Goldblatt works for me. Accidentially, I have Goldblatt here, although I didn't read it before -- you agree with me it's far away from every day's common sense, even for a hobby coder?? I mean, this is not «Head first categories», is it? ;-)) With «every day's common sense» I did not mean «a mathematician's every day's common sense», but that of, e.g., a housewife or a child... But I have became curious now for Goldblatt... * the definition of open/closed sets in topology with the boundary elements of a closed set to considerable extent regardable as facing to an «outside» (so that reversing these terms could even appear more intuitive, or «bordered» instead of closed and «unbordered» instead of open), Both have a border, just in different places. Which elements form the border of an open set?? As an example, let's play a little: Arrows: Arrows are more fundamental than objects, in fact, categories may be defined with arrows only. Although I like the term arrow (more than 'morphism'), I intuitively would find the term «reference» less contradictive with the actual intention, as this term Arrows don't refer. A *referrer* (object) refers to a *referee* (object) by a *reference* (arrow). Categories: In every day's language, a category is a completely different thing, without the least Not necesssarily (for Kantians, Aristoteleans?) Are you sure...?? See http://en.wikipedia.org/wiki/Categories_(Aristotle) ... If memory serves, MacLane says somewhere that he and Eilenberg picked the term "category" as an explicit play on the same term in philosophy. In general I find mathematical terminology well-chosen and revealing, if one takes the trouble to do a little digging. If you want to know what terminological chaos really looks like try linguistics. ;-) For linguistics, granted... In regard of «a little digging», don't you think terminology work takes a great share, especially at interdisciplinary efforts? Wouldn't it be great to be able to drop, say 20% or even more, of such efforts and be able to progress more fluidly ? -g _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 3

The Related monad and constant values in type classes
by Jonas Almström Duregård 18 Feb '10

18 Feb '10

Hi, This literate haskell file was intended to be a quick question about a problem i have been pondering, but it developed into a short presentation instead. What i want to know is if there is already something like this (and suggestions for improvement of course). >{-#LANGUAGE GeneralizedNewtypeDeriving#-} Sometimes i find myself needing to associate a constant with a type or, more precisely, with a type class instance. Something like this would be nice: class Sized a where size :: Int instance Sized Int where size = 32 Of course this will not work since there is no way of knowing which instance i refer to when i use "size". A common work-around is to use a dummy parameter: >class SizedDummy a where > sizeDummy :: a -> Int > >instance SizedDummy Int where > sizeDummy = const 32 The size function is typically passed an undefined value. This is not very pretty, and somewhat unsafe. Another workaround is to define a newtype with a type parameter. >newtype SizeOf a = MkSize {toInt :: Int} >class SizedNewType a where > sizeNewType :: SizeOf a > >instance SizedNewType Int where > sizeNewType = MkSize 32 If we want the size of a pair to be the sum of it's components, something like this is needed: >instance (SizedNewType a, SizedNewType b) => SizedNewType (a,b) where > sizeNewType = sizeNewType' sizeNewType sizeNewType where > sizeNewType' :: SizeOf a -> SizeOf b -> SizeOf (a,b) > sizeNewType' a b = MkSize $ toInt a + toInt b This is way to much code say that "size = size a + size b". A more general solution can be achieved by making "Int" another type variable of "SizeOf". I call the resulting type "Related": >newtype Related a b = Related {unrelated :: b} deriving > (Eq,Ord,Show,Read,Bounded,Enum,Fractional,Num, > Real,Integral,RealFrac,Floating,RealFloat) This type is highly reusable and the GeneralizedNewtypeDeriving language extension is very practical (although the instances could be written manually). It can also be used as an Identity monad: >instance Functor (Related a) where > fmap f (Related a) = Related $ f a > >instance Monad (Related a) where > return = Related > (Related a) >>= f = f a This allows the Sized class and instances to be specified in a slim fashion using a familiar monadic interface: >class Sized a where > size :: Related a Int > >instance Sized Int where > size = return 32 > >instance (Sized a, Sized b) => Sized (a,b) where > size = do > a <- return size :: Sized a => Related (a,b) (Related a Int) > b <- return size :: Sized b => Related (a,b) (Related b Int) > return $ unrelated a + unrelated b This still requires a lot of type signatures, some additional magic is required. It is possible to write general versions of the type signatures above, which allows the following instance definition for (,,): >instance (Sized a, Sized b, Sized c) => Sized (a,b,c) where > size = do > a <- on3 size > b <- on2 size > c <- on1 size > return $ a + b + c With the derivation of Num, this can be done even more compact: >instance (Sized a, Sized b, Sized c, Sized d) => Sized (a,b,c,d) where > size = on1 size + on2 size + on3 size + on4 size The code for the onN functions: >rerelate :: Related a b -> Related c b >rerelate = return . unrelated >on1 :: Related a v -> Related (x a) v >on1 = rerelate >on2 :: Related a v -> Related (x a x0) v >on2 = rerelate >on3 :: Related a v -> Related (x a x0 x1) v >on3 = rerelate >on4 :: Related a v -> Related (x a x0 x1 x2) v >on4 = rerelate Regards, Jonas Almström Duregård

4 4

How can i run darcs in ghci?
by Daryoush Mehrtash 18 Feb '10

18 Feb '10

I am trying to load darc.hs (from darcs 2.3.1, ghci 6.10.4 on Ubuntu) and I get the following :~/darcs-src/darcs-2.3.1/src$ ghci GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> :load darcs Darcs/RepoPath.hs:59:0: error: impossible.h: No such file or directory phase `C pre-processor' failed (exitcode = 1) > What am I doing wrong? Thanks, Daryoush

3 4

CURL and threads
by Eugene Dzhurinsky 18 Feb '10

18 Feb '10

Hello, all! Can somebody please explain, what is the best way of using CURL with several threads? I wrote simple client, which tries to authenticate against HTTP server. With running this client, it starts to eat memory insanely (and I know this code is far, far away of even being close to be called good one ) ========================================================================================= module NTLMTest where import System.IO import Network.Curl import Control.Concurrent import Control.Concurrent.Chan type ResponseState = Either Bool String type RespChannel = Chan ResponseState delay = 500 * 1000 isResponseOk :: String -> CurlResponse -> ResponseState isResponseOk username response = case respCurlCode response of CurlOK -> Left True _ -> Right $ username ++ " => " ++ respStatusLine response ++ " :: " ++ (show . respStatus $ response) checkAuthResponse :: RespChannel -> String -> String -> String -> IO () checkAuthResponse state user passwd url = do response <- curlGetResponse_ url [CurlHttpAuth [HttpAuthAny], CurlUserPwd $ user ++ ":" ++ passwd] writeChan state $ isResponseOk user response threadDelay $ delay runHTTPThread :: RespChannel -> (String,String) -> IO () runHTTPThread state (user,passwd) = checkAuthResponse state user passwd url url = "http://localhost:8082/" credentials = map (\i -> ("user" ++ show i,"123456")) [1..21] main = withCurlDo $ do chan <- newChan :: IO (RespChannel) mapM_ ( \cred -> forkIO $ runHTTPThread chan cred ) credentials dumpChannel chan $ length credentials main where dumpChannel :: RespChannel -> Int -> IO () dumpChannel _chan n | n == 0 = return () | otherwise = do state <- readChan _chan case state of (Left _) -> return () --putStrLn "OK" (Right err) -> putStrLn err dumpChannel _chan $ n-1 ========================================================================================= If I get rid of forkIO - it stops at 40-50 megabytes and don't raise memory usage anymore. Also, I noticed that (either because of buffering, or may be something else) results are appearing on console much slower than if I simply use "wget" with looping in shell script. JMeter also reports awesome speed, so server can authenticate tens of concurrent users per second (thus it's not server or connection bandwidth issue). Hopefully, someone could help me in overcoming my ignorance :) -- Eugene N Dzhurinsky

3 2

ANN: iteratee-parsec 0.0.1
by Maciej Piechotka 18 Feb '10

18 Feb '10

Iteratee-parsec is a library which allows to have a parsec (3) parser in IterateeG monad. It contains 2 implementations: - John Lato's on public domain. It is based on monoid and design with short parsers in mind. - Mine on MIT. It is based on single-linked mutable list. It seems to be significantly faster for larger parsers - at least in some cases - but it requires a monad with references (such as for example IO or ST). Regards

1 0

Re : Friedberg numberings
by Pierre-Etienne Meunier 18 Feb '10

18 Feb '10

Hi, In fact it is not quite hard to see that such a numbering exists : just take any numbering of all Turing machines, say {\phi_i}, then remove all indices i such that there is j<i such that \phi_j = \phi_i (equality is mathematically correctly defined between functions from N to N). Ah, and also, notice that what you call a "programming language" is nothing else than an enumeration of all Turing machines. However, if by "construction" you meant "recursive construction", i.e. for another enumeration (\psi_i), find a Turing machine computing for any i, the index j such that \phi_j=\psi_i, then it is clear that it is not possible : it would allow to decide the equality problem for Turing machines. Hope this helps...

1 0

Friedberg numberings.
by Grigory Sarnitskiy 18 Feb '10

18 Feb '10

Hello! The question is not about Haskell, but I don't know where else to ask. In the book "Computable functions" by Vereshchagin and Shen it is said that "it is possible to invent a programming language such that each programming problem has a unique solution in it". The author claims that this statement is a rewording of the theorem, that there is a universal computable function, such that any computable function has exactly one number. I wonder has such language been actually constructed? the book itself (look at the bottom of p 30 for the statement): http://books.google.ru/books?id=A6uvsks0abgC&pg=PA30#v=onepage&q=&f=false

1 0