- Haskell-Cafe - Haskell.org

another laziness blowup (this one unsolved)
by Thomas Hartman 17 Jul '09

17 Jul '09

Is it possible to fix alternate' (the second version), or otherwise define a fast stepwise alternate that doesn't blow up on long lists? alternate just breaks up [1,2,3,4,5] into ([1,3,5],[2,4]) Thanks! {-# LANGUAGE BangPatterns #-} import Data.List import Control.Arrow import Control.Parallel.Strategies t = (last *** last) $! alternate $ [1..(10^6)] t' = (last *** last) $! alternate' $ [1..(10^6)] t'' = (last *** last) $! alternate'' $ [1..(10^6)] -- finishes reasonably fast, but does a separate computation for the list and its tail rather than just rip through it alternate x = (skip1 x,(skip1 $ tail x)) skip1 = skip 1 skip n xs = let (a,b) = splitAt (n+1) xs in case a of [] -> [] x:_ -> x : skip n b -- this one overflows on million element list, even after fiddling with strictness on input args. can this be fixed? alternate' xs = let f3 :: Int -> (([Int],[Int]),Int) -> (([Int],[Int]),Int) f3 x ((a,b),n) = -- rnf (x,((a,b),n)) `seq` let nxtn = n+1 in if n `mod` 2 == 0 then ((x:a,b),nxtn) else ((a,x:b),nxtn) in fst . foldr f3 (([],[]),0) $ xs -- no overflow, goes through the list stepwise, but it's actually slightly slower than the first alternate because of the reverses alternate'' xs = let f3 ((a,b),n) x = (let nxtn = n+1 in if n `mod` 2 == 0 then ((x:a,b),nxtn) else ((a,x:b),nxtn) ) in (reverse *** reverse) . fst . foldl' f3 (([],[]),0) $ xs

1 1

Re: [Haskell-cafe] Leaner Haskell.org frontpage
by haskell＠kudling.de 16 Jul '09

16 Jul '09

I never said we should only expose 7 links. Take for example the task "Find out more about this Haskell i heared about". You would need to scan the right half of the front page and you need to scan the left part of the page. There you need to scan "About", it could be explained under "Why use Haskell?" or "Language definition" or "Haskell in 5 steps" or "Learning Haskell" or "Wiki articles" or "Blog articles and news". Where should i look? I have to scan a lot of text, i have to keep a lot of options in mind and for my taste the load is too much. Be my limit 7 or 20 links. haskell(a)kudling.de wrote: > Most people feel overwhelmed when confronted with more than 7+-2 items: > http://www.smashingmagazine.com/2007/10/09/30-usability-issues-to-be-aware-… This refers to the number of items/things people can remember in their short-time memory. This has nothing to do with the maximum number of menu items you should use. There is of course a limit, but there is no reason to limit it to 7+-2. Cheers, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

11 16

Applying different functions to different types for lists
by Szekeres István 16 Jul '09

16 Jul '09

Hi, I want to build a framework to apply different functions to different types of lists and I want to generalize the solution as much as possible but my Haskell knowledge is not really enough to do this (I'm a haskell novice). The problem has two dimensions: 1. Lets say I have two functions: r13, ul : Char -> Char where r13 returns the rot13ed character, and ul converts upper case chars to lower case and vice versa. Later I want a rot13 function that can operate on different types of lists and an uxl function that can also operate on different types of lists. 2. Lets say I have two kinds of lists to handle: String and Data.ByteString.Lazy as L. For Strings I want the updater function to be used for each character and for L I want all items to be converted to Char, the updater function to be updated and the result to be converted back to the original item type. Therefore I define a common class for handling these lists: class ListUpdater a where updateFn :: Char -> Char update :: a -> a so I can define the update function for the different types of lists: instance ListUpdater String where update = map updateFn instance ListUpdater L.ByteString where update = L.pack . (map updateFn) . L.unpack But now how should I glue these 2 dimensions together? How to say that I want a rot13 function that applies to any data type instantiated from ListUpdater and that is using the r13 function to do the update? And also that I want an uxl function that also applies to any data type instantiated from ListUpdater and that is using the ul function to do the update? Thanks, Istvan

2 1

IFL 2009: Third Call for Papers
by IFL 2009 16 Jul '09

16 Jul '09

1 0

Pattern matching does not work like this?
by Magicloud Magiclouds 16 Jul '09

16 Jul '09

Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error. -- 竹密岂妨流水过山高哪阻野云飞

11 13

Re: Problems with nested Monads
by John Lato 16 Jul '09

16 Jul '09

If M is a monad transformer (e.g. StateT) and able to be parameterised over an arbitrary monad, you can do something related, which may actually be more useful to you. Given the definition of StateT from mtl: newtype StateT s m a = StateT { runStateT :: s -> m (a, s) } you could define this join-like function: join2 :: (Monad n) => n (StateT s n a) -> StateT s n a join2 m = StateT (\state -> m >>= flip runStateT state) (I don't know a good name for this function; it's called "joinIM" in iteratee) Perhaps this would apply to your situation? Cheers, John Lato > > Message: 18 > Date: Fri, 10 Jul 2009 17:25:55 -0400 > From: Job Vranish <jvranish(a)gmail.com> > Subject: Re: [Haskell-cafe] Problems with nested Monads > To: Edward Kmett <ekmett(a)gmail.com> > Cc: Haskell Cafe mailing list <haskell-cafe(a)haskell.org> > Message-ID: > <ed4cefb50907101425w118990e2x5d6585582157e08f(a)mail.gmail.com> > Content-Type: text/plain; charset="iso-8859-1" > > Yeah, I think the problem with my case is that while M is a specific monad > (essentially StateT), N can be an arbitrary monad, which I think destroys my > changes of making a valid joinInner/joinOuter/distribute. > Maybe someday Haskell will infer valid joinInner/joinOuter for simple cases > :D > Thanks for you help. I'll definitely have to see if I can find that paper. > > - Job Vranish > > On Fri, Jul 10, 2009 at 3:09 PM, Edward Kmett <ekmett(a)gmail.com> wrote: > >> The problem you have is that monad composition isn't defined in general. >> You would need some form of distributive law either for your monads in >> general, or for your particular monads wrapped around this particular kind >> of value. >> >> What I would look for is a function of the form of one of: >> >> distribute :: N (M a) -> M (N a) >> joinInner :: M (N (M a)) -> M (N a) >> joinOuter :: N (M (N a)) -> M (N a) >> >> that holds for your partiular monads M and N. >> >> IIRC Mark P. Jones wrote a paper or a lib back around '93 that used these >> forms of distributive laws to derive monads from the composition of a monad >> and a pointed endofunctor. >> >> -Edward Kmett >> >> On Fri, Jul 10, 2009 at 11:34 AM, Job Vranish <jvranish(a)gmail.com> wrote: >> >>> I'm trying to make a function that uses another monadic function inside a >>> preexisting monad, and I'm having trouble. >>> Basically my problem boils down to this. I have three monadic functions >>> with the following types: >>> f :: A -> M B >>> g :: B -> N C >>> h :: C -> M D >>> (M and N are in the monad class) >>> I want a function i where >>> i :: A -> M (N D) >>> >>> the best I can come up with is: >>> i :: A -> M (N (M D)) >>> i a = liftM (liftM h) =<< (return . g) (f a) >>> >>> I'm starting to feel pretty sure that what I'm going for is impossible. Is >>> this the case? >>> _______________________________________________ >>> Haskell-Cafe mailing list >>> Haskell-Cafe(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>>

1 0

homomorphic encryption and monads?
by Jason Dagit 15 Jul '09

15 Jul '09

Hello, I have just a very vague understanding of what homomorphic encryption is, but I was wondering if homomorphic encryption behaves as a one-way monad (like IO). So for example, suppose you wrote a function that worked on encrypted email to determine if it spam, maybe it looks like this: isSpam :: Cypher String -> Cypher Bool I could be mistaken about the way this works, but it seems that isSpam can't return a plain 'Bool' because then you could know things about the encrypted data without having to decrypt it first. So that is why I think it has to return "Cypher Bool". And because it's a homomorphic encryption, you could have something like doWork: doWork :: Cypher a -> (a -> b) -> Cypher b Which we could use to implement isSpam: isSpam s = doWork s spamTest where spamTest :: String -> Bool I initially thought that doWork should be (>>=), but it seems the type of the function should either be (a -> b) or (Cypher a -> Cypher b). That is, return :: a -> Cypher a, is not available. All the data should already be encrypted. Thinking about it a bit more, since we never have to decrypt the data to work with it, it seems that (a -> b) is wrong as well, because we don't have the key or whatever to do the decrypting. So, then it seems reasonable that the only type for doWork is this: doWork :: Cypher a -> (Cypher a -> Cypher b) -> Cypher b Which doesn't really seem all that useful now. On the other hand, maybe we have an algorithm which can take a function on normal values and gives us a function on Cypher values: enCypher :: (a -> b) -> Cypher a -> Cypher b Or perhaps, it should be: enCypher :: (a -> b) -> Cypher (a -> b) Which would match the type of return. If that is the type of return, then we probably want: (>>=) :: Cypher (a -> b) -> ((a -> b) -> Cypher (c -> d)) -> Cypher (c -> d) At this point, I'm not actually sure if the second type for enCypher makes any sense. But, if it does, then I think it says the purpose of the monad is to act on the transformations and not the data. That is, instead of focusing on the data as being held in the cypher, we are thinking of the functions as being transformed into a cypher space. Has anyone else been thinking about this? Jason

3 2

ANNOUNCE: generator
by Yair Chuchem 15 Jul '09

15 Jul '09

A new "generator" package has been uploaded to Hackage. It implements an alternative list monad transformer, a list class, and related functions. The difference from mtl/transformers's ListT is that mtl is a monadic action that returns a list: newtype ListT m a = ListT { runListT :: m [a] } generator's is a monadic list: data ListItem l a = Nil | Cons { headL :: a, tailL :: l a } newtype ListT m a = ListT { runListT :: m (ListItem (ListT m) a) } A short example program which reads numbers from the user and interactively sums them up: import Control.Monad.ListT (ListT) import Data.List.Class (execute, joinM, repeat, scanl, takeWhile) import Prelude hiding (repeat, scanl, takeWhile) main = execute . joinM . fmap print . scanl (+) 0 . fmap (fst . head) . takeWhile (not . null) . fmap reads . joinM $ (repeat getLine :: ListT IO (IO String)) I also wrote an example/blog-post about using ListT to add an undo option to the classic game of "hamurabi": http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.ht… Another interesting observation is that "ListT [] a" is a tree of "a"s. The module Data.List.Tree includes functions to prune and search such trees (dfs, bfs, bestFirstSearchOn, etc). This can be useful for modularizing code that uses the list monad for combinatoric search by decoupling tree creation from processing and pruning.

1 0

ANN: shelltestrunner 0.6 released
by Simon Michael 15 Jul '09

15 Jul '09

(and, the original which I didn't cc to -cafe.) I'm pleased to announce the first release of shelltestrunner: a small tool for testing any command-line program by running it through "shell" tests defined with a simple file format. Each test can specify the command-line arguments, input, expected output, expected stderr output, and/or expected exit code. This was extracted from the hledger project, inspired by the tests in John Wiegley's ledger project, and uses Max Bolingbroke's test- framework. In some cases you will get a big speedup by using test- framework's parallelising feature. Example: $ shelltestrunner shelltestrunner *.test -- -j8 :args.test:1: [OK] :args.test:2: [OK] :args.test:3: [OK] :args.test:4: [OK] :early-j-option.test: [OK] :help-flag.test: [OK] etc. I hope you find it useful. Feedback, patches, or alternate packaging suggestions are welcome! Best, -Simon

1 0

Re: ANN: shelltestrunner 0.6 released
by Simon Michael 15 Jul '09

15 Jul '09

And the urls: home - http://hackage.haskell.org/package/shelltestrunner darcs repo - http://joyful.com/repos/shelltestrunner

1 0