- Haskell-Cafe - Haskell.org

Dynamic Programming with Data.Vector
by Myles C. Maxfield 18 Sep '12

18 Sep '12

Hello, I've been writing dynamic programming (dp) algorithms in imperative languages for years, and I was thinking recently about how to use it in a Haskell context. In particular, I want to write a function that takes an ordered collection of items and produces a new item to insert into the ordered collection. The most straightforward way to do this would be to use a list, something like the following: recurse :: [Integer] -> [Integer] recurse l = newValue : recurse (take (length l + 1) infiniteList) where newValue = ... infiniteList :: [Integer] infiniteList = initialList ++ recurse initialList where initialList = ... solution :: Integer solution = infiniteList !! 5 I'm assuming that this can run fast because I'm assuming the 'take' function won't actually duplicate the list ([1] doesn't actually list the running time of 'take') Is this a correct assumption to make? Secondarily, and most importantly for me, I'm curious about how to make this fast when the computation of 'newValue' requires random access to the inputted list. I'm assuming that I would use Vectors instead of lists for this kind of computation, and [2] describes how I can use the O(1) 'slice' instead of 'take' above. However, both of Vector's cons and snoc functions are O(n) which defeats the purpose of using this kind of algorithm. Obviously, I can solve this problem with mutable vectors, but that's quite inelegant. Overall, I'm looking for a function, similar to Data.Vector's 'generate' function, but instead of the generation function taking the destination index, I'd like it to take the elements that have previously been constructed. Is there such a function? If there isn't one, is this kind of function feasible to write? If such a function doesn't exist and is feasible to write, I'd be happy to try to write and contribute it. [1] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#g… [2] http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vect…

2 4

Re: [Haskell-cafe] What is the good way to work with list comprehension and UTCTime?
by Chris Heller 18 Sep '12

18 Sep '12

You might want to have a look at the time-recurrence package: http://hackage.haskell.org/package/time-recurrence For your simple cases you would do something like: Each second: starting (UTCTime ...) $ recur secondly Each minute: starting (UTCTime ...) $ recur minutely The rules can get quite a bit more complex than that. I am the author of time-recurrence, so if you have questions feel free to ping me. -Chris On Fri, Sep 14, 2012 at 6:00 AM, <haskell-cafe-request(a)haskell.org> wrote: > Send Haskell-Cafe mailing list submissions to > haskell-cafe(a)haskell.org > > To subscribe or unsubscribe via the World Wide Web, visit > http://www.haskell.org/mailman/listinfo/haskell-cafe > or, via email, send a message with subject or body 'help' to > haskell-cafe-request(a)haskell.org > > You can reach the person managing the list at > haskell-cafe-owner(a)haskell.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Haskell-Cafe digest..." > > > Today's Topics: > > 1. Fwd: How Type inference work in presence of Functional > Dependencies (Dan Doel) > 2. Re: [ANN] Cumino 0.2 - Now supports pretty indentation > through stylish-haskell (Brandon Allbery) > 3. Re: [ANN] Cumino 0.2 - Now supports pretty indentation > through stylish-haskell (Alfredo Di Napoli) > 4. ANNOUNCE: Groundhog 0.1.0.1 - high-level database library > (Boris Lykah) > 5. Re: ANNOUNCE: Groundhog 0.1.0.1 - high-level database library > (Tom Murphy) > 6. Re: Either Monad and Laziness (wren ng thornton) > 7. How do I generate random numbers using random-fu, with > platform-agnostic code? (Andrew Pennebaker) > 8. Is Hackage down? (C K Kashyap) > 9. Re: Is Hackage down? (damodar kulkarni) > 10. What is the good way to work with list comprehension and > UTCTime? (Magicloud Magiclouds) > 11. Re: What is the good way to work with list comprehension and > UTCTime? (Karl Voelker) > 12. Re: [ANN] Cumino 0.2 - Now supports pretty indentation > through stylish-haskell (Alfredo Di Napoli) > 13. Re: Is Hackage down? (John Wiegley) > 14. Re: [ANN] Cumino 0.2 - Now supports pretty indentation > through stylish-haskell (Alfredo Di Napoli) > 15. Re: What is the good way to work with list comprehension and > UTCTime? (Roman Cheplyaka) > 16. Re: What is the good way to work with list comprehension and > UTCTime? (Magicloud Magiclouds) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Thu, 13 Sep 2012 10:44:17 -0400 > From: Dan Doel <dan.doel(a)gmail.com> > Subject: [Haskell-cafe] Fwd: How Type inference work in presence of > Functional Dependencies > To: Haskell Caf? List <haskell-cafe(a)haskell.org> > Message-ID: > < > CAHEA9tPsGTUX4Ke9eGCpA%2B-f_b_Ky9--y6RZkHPAmN9LW8MxHA(a)mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > Copying the mailing list, because I forgot. > > On Thu, Sep 13, 2012 at 5:18 AM, satvik chauhan <mystic.satvik(a)gmail.com> > wrote: > > Consider the code below : > > > > {-# LANGUAGE > > > MultiParamTypeClasses,FlexibleInstances,FunctionalDependencies,UndecidableInstances,FlexibleContexts > > #-} > > class Foo a c | a -> c > > instance Foo Int Float > > f :: (Foo Int a) => Int -> a > > f = undefined > > > > Now when I see the inferred type of f in ghci > > > >> :t f > > > >> f :: Int -> Float > > > > Now If I add the following code > > > > g :: Int -> Float > > g = undefined > > > > h :: (Foo Int a) => Int -> a > > h = g > > > > > > I get the error > > > > Could not deduce (a ~ Float) > > > > > > I am not able to understand what has happened here ? The restriction "Foo > > Int a" should have restricted the type of h to "Int -> Float" as shown in > > the inferred type of f. > > The answer, I believe, is that the difference between the fundep > implementation and type families is local constraint information. > Fundeps do no local propagation. > > So in your first definition, you've locally provided 'Int -> a', which > is acceptable to GHC. Then it figures out externally to the function > that '(Foo Int a) => Int -> a' is actually Int -> Float. > > In the second definition, you're trying to give 'Int -> Float', but > GHC only knows locally that you need to provide 'Int -> a' with a > constraint 'Foo Int a' which it _won't_ use to determine that a ~ > Float. > > This is not inherent to fundeps. One could make a version of fundeps > that has the local constraint rules (easily so by translating to the > new type families stuff). But, the difference is also the reason that > overlapping instances are supported for fundeps and not type families. > But I won't get into that right now. > > -- Dan > > > > ------------------------------ > > Message: 2 > Date: Thu, 13 Sep 2012 11:20:51 -0400 > From: Brandon Allbery <allbery.b(a)gmail.com> > Subject: Re: [Haskell-cafe] [ANN] Cumino 0.2 - Now supports pretty > indentation through stylish-haskell > To: Alfredo Di Napoli <alfredo.dinapoli(a)gmail.com> > Cc: Ray <i(a)maskray.tk>, haskell-cafe <haskell-cafe(a)haskell.org> > Message-ID: > <CAKFCL4WAtx6R0NVtP7nxnj1ZFp= > KHDx1dGeO-s9EsG4H9nMsvQ(a)mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > On Thu, Sep 13, 2012 at 2:22 AM, Alfredo Di Napoli < > alfredo.dinapoli(a)gmail.com> wrote: > > > urxvtc -e sh -c 'echo a' > >> xterm -e echo a > >> > > > > I would like to, and in fact I've already tried, but urxvt is trickier > > than other shells. Using the command you gave me does not create a new > > window, tested both on XMonad and Gnome. This is > > the error you can see using the option "-hold", this way: > > > > urxvt --hold -e "echo a" > > > > This opens a new window with the error: *urxvt: Unable to exec child. > > * > > > > I think you misunderstood; as I read it (and as I would expect it to work > given the above descrtiption) that would be > > urxvt --hold -e sh -c 'echo a' > > -- > brandon s allbery allbery.b(a)gmail.com > wandering unix systems administrator (available) (412) 475-9364 vm/sms >

5 4

Re: [Haskell-cafe] Either Monad and Laziness
by John Lato 17 Sep '12

17 Sep '12

> Subject: Re: [Haskell-cafe] Either Monad and Laziness > > On 9/14/12 5:16 PM, Eric Velten de Melo wrote: >> But now I'm kinda lost. Is there an easy way to explain the difference between: >> -iteratee >> -conduit >> -enumerator I tend to group them into three families. 'iteratee' and 'enumerator' are fairly directly drawn from Oleg's code, with mostly implementation differences (at least when compared to the other families). They've tended to keep Oleg's original names (iteratee, enumerator, enumeratee). The biggest user-visible difference between iteratee and enumerator is the level of datastream abstraction. iteratee abstracts over the stream, and enumerator abstracts over elements of the stream. The stream is explicitly a list of elements. This exposes some of the details of data chunking to the user, which has both advantages and disadvantages (iteratee exposes this also, but it's not necessary as is the case for enumerator). The second family (chronologically) includes conduit and (maybe) iterIO. I've written a little about this group at http://johnlato.blogspot.sg/2012/06/understandings-of-iteratees.html Although they serve the same goals in spirit, the implementation may or may not necessarily be an iteratee/enumerator arrangement (e.g. conduit). This is a technical observation, not a criticism, depending on exactly what you consider to define the style in the first place. This group has usually renamed functions. I discuss some of the other differences on my blog. The third familiy is all the pipes-* stuff. This group tends towards emphasizing the relationship between iteratee/enumerator pairs and coroutines, and also emphasizing (to use Oleg terminology) composition of enumeratees. I've been meaning to write more about this group, but thus far have been unable to do so. I'd rather not hijack by evangelizing, but obviously I think iteratee provides several important advantages over the other options. John L.

1 0

guards in applicative style
by felipe zapata 17 Sep '12

17 Sep '12

Hi Haskellers, Suppose I have two list and I want to calculate the cartesian product between the two of them, constrained to a predicate. In List comprehension notation is just result = [ (x, y) | x <- list1, y <-list2, somePredicate x y ] or in monadic notation result = do x <- list1 y <- list2 guard (somePredicate x y) return $ (x,y) Then I was wondering if we can do something similar using an applicative style result = (,) <$> list1 <*> list2 (somePredicate ???) The question is then, there is a way for defining a guard in applicative Style? Thanks in advance, Felipe Zapata.

5 4

Transforming a ADT to a GADT
by Florian Lorenzen 17 Sep '12

17 Sep '12

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello cafe, I have a question wrt. to GADTs and type families in GHC (7.6.1). I'd like to transform a value of an ADT to a GADT. Suppose I have the simple expression language > data Exp = Lit Int > | Succ Exp > | IsZero Exp > | If Exp Exp Exp and the GADT > data Term t where > TLit :: Int -> Term Int > TSucc :: Term Int -> Term Int > TIsZero :: Term Int -> Term Bool > TIf :: Term Bool -> Term ty -> Term ty -> Term ty that encodes the typing rules. Now, I'd like to have a function > typecheck :: Exp -> Maybe (Term t) > typecheck exp = <...> that returns the GADT value corresponding to `exp' if `exp' is type correct. I found a solution at http://okmij.org/ftp/tagless-final/TypecheckedDSLTH.hs but this has as type (slightly adapted) > typecheck :: Exp -> Maybe TypedTerm with > data TypedTerm = forall ty. (Typ ty) (Term ty) > data Typ ty = > TInt Int | TBool Bool That is, the GADT value is hidden inside the existential and cannot be unpacked. Therefore, I cannot write a type preserving transformation function like > transform :: Term t -> Term t that gets the result of the `typecheck' function as input. The solution mentioned above uses Template Haskell to extract the `Term t' type from the existential package and argues that type errors cannot occur during splicing. Is there a possibility to avoid the existential and hence Template Haskell? Of course, the result type of typecheck depends on the type and type correctness of its input. My idea was to express this dependency by parameterizing `Exp' and using a type family `ExpType' like: > typecheck :: Exp e -> Maybe (Term (ExpType e)) > typecheck (ELit > i) = Just (TLit i) > typecheck (ESucc exp1) = case typecheck exp1 of > Nothing -> Nothing > Just t -> Just (TSucc t) > <...> with > data TEXP = L | S TEXP | IZ TEXP | I TEXP TEXP TEXP -- datakind > > > data Exp (e::TEXP) where > ELit :: Int -> Exp L > ESucc :: Exp e1 -> Exp (S e1) > EIsZero :: Exp e1 -> Exp (IZ e1) > EIf :: Exp e1 -> Exp e2 -> Exp e3 -> Exp (I e1 e2 e3) It seems to me that `ExpType' then would be a reification of the type checker for `Exp' at the type level. But I did not know how to define it. Does it make sense at all? Is it possible in GHC? All the examples on the net I looked at either start with the GADT right away or use Template Haskell at some point. So, perhaps this `typecheck' function is not possible to write in GHC Haskell. I very much appreciate any hints and explanations on this. Best regards, Florian - -- Florian Lorenzen Technische Universität Berlin Fakultät IV - Elektrotechnik und Informatik Übersetzerbau und Programmiersprachen Sekr. TEL12-2, Ernst-Reuter-Platz 7, D-10587 Berlin Tel.: +49 (30) 314-24618 E-Mail: florian.lorenzen(a)tu-berlin.de WWW: http://www.user.tu-berlin.de/florenz/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://www.enigmail.net/ iEYEARECAAYFAlBTCr8ACgkQvjzICpVvX7ZfTgCeOPflPtaEW/w1McjYWheaRaqq oUQAnRXSrGP3se+3oiI3nnd+B/rK8yx8 =X1hR -----END PGP SIGNATURE-----

5 9

Re: [Haskell-cafe] Transforming a ADT to a GADT
by oleg＠okmij.org 17 Sep '12

17 Sep '12

Florian Lorenzen wrote: > Now, I'd like to have a function > > typecheck :: Exp -> Maybe (Term t) > > typecheck exp = <...> > that returns the GADT value corresponding to `exp' if `exp' is type > correct. Let us examine that type: typecheck :: forall t. Exp -> Maybe (Term t) Do you really mean that given expression exp, (typecheck exp) should return a (Maybe (Term t)) value for any t whatsoever? In other words, you are interested in a type-*checking* problem: given an expression _and_ given a type, return Just (Term t) if the given expression has the given type. Both expression and the type are the input. Incidentally, this problem is like `read': we give the read function a string and we should tell it to which type to parse. If that is what you mean, then the solution using Typeable will work (although you may prefer avoiding Typeable -- in which case you should build type witnesses on your own). > that returns the GADT value corresponding to `exp' if `exp' is type > correct. Your comment suggests that you mean typecheck exp should return (Just term) just in case `exp' is well-typed, that is, has _some_ type. The English formulation of the problem already points us towards an existential. The typechecking function should return (Just term) and a witness of its type: typecheck :: Exp -> Sigma (t:Type) (Term t) Then my > data TypedTerm = forall ty. (Typ ty) (Term ty) is an approximation of the Sigma type. As Erik Hesselink rightfully pointed out, this type does not preclude type transformation functions. Indeed you have to unpack and then repack. If you want to know the concrete type, you can pattern-match on the type witness (Typ ty), to see if the inferred type is an Int, for example. Chances are that you wanted the following typecheck :: {e:Exp} -> Result e where Result e has the type (Just (Term t)) (with some t dependent on e) if e is typeable, and Nothing otherwise. But this is a dependent function type (Pi-type). No wonder we have to go through contortions like Template Haskell to emulate dependent types in Haskell. Haskell was not designed to be a dependently-typed language.

2 1

[ANNOUNCE] Juicy.Pixels v2.0
by Vincent Berthoux 16 Sep '12

16 Sep '12

Hello, I'm pleased to announce the release of Juicy.Pixels (a pure Haskell library for image loading and writing) in version 2.0. The new features of this version are a Gif file decoder, and a rework of the plane extraction part to be type safe github: https://github.com/Twinside/Juicy.Pixels hackage: http://hackage.haskell.org/package/JuicyPixels Thanks Vincent Berthoux

1 0

Could not find module `Text.Regex'
by zaxis 16 Sep '12

16 Sep '12

import Text.Regex date_by_ntday dateStr ntday = do let [y,m,d] = map (\x -> read x::Int) $ splitRegex (mkRegex "-") dateStr .... %ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 Which package(s) do i need to use Text.Regex ? Sincerely! ----- fac n = foldr (*) 1 [1..n] -- View this message in context: http://old.nabble.com/Could-not-find-module-%60Text.Regex%27-tp27366745p273… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

5 5

Invitation to connect on LinkedIn
by Sakari Joinen via LinkedIn 16 Sep '12

16 Sep '12

LinkedIn ------------ Sakari Joinen requested to add you as a connection on LinkedIn: ------------------------------------------ Steve, I'd like to add you to my professional network on LinkedIn. - Sakari Accept invitation from Sakari Joinen http://www.linkedin.com/e/uc6lxc-h70llpqy-2x/XvIdBwmueHfd6vFMPXXdLaqreCbl5o… View profile of Sakari Joinen http://www.linkedin.com/e/uc6lxc-h70llpqy-2x/rso/203924390/GIO8/name/259079… ------------------------------------------ You are receiving Invitation emails. This email was intended for Steve Severance. Learn why this is included: http://www.linkedin.com/e/uc6lxc-h70llpqy-2x/plh/http%3A%2F%2Fhelp%2Elinked… (c) 2012, LinkedIn Corporation. 2029 Stierlin Ct, Mountain View, CA 94043, USA.

6 5

ANN: darcsden-1.0
by Simon Michael 15 Sep '12

15 Sep '12

I'm pleased to announce the release of darcsden 1.0! darcsden is a web application for browsing and managing darcs repositories (and issue trackers, and their owners), and an SSH server which lets users push changes to the app without needing a full system login. It can be used for browsing your local repositories, for publishing your repos on the web, or for running a public repo hosting site. It is available under the BSD license. darcsden was created by Alex Suraci. The last release was 0.5, in 2010. I've been tinkering with it and using it to publish repos on my site for a while. In recent months, with help from the Darcs community I made a serious attempt to make it more robust and to run a reliable instance at http://hub.darcs.net , with promising results. Alex and I feel this is a good time to release an official darcsden 1.0, containing hub's reliability/functionality updates (but not the UI style tweaks). Home: http://hackage.haskell.org/package/darcsden Release notes: -------------- Changes in this release fall into several themes: Deployability/Hackability * dependencies have been updated; darcsden now uses the latest GHC, darcs and snap * cabal build flags have been added: - darcs28: build with released darcs 2.8.2+ instead of latest darcs-screened ? default: true - ssh, closing, highlighting: build the ssh server, issue-closing script, and highlighting features ? default: true (disable these for easier building on windows) * settings allowing easier custom deployment are available in src/DarcsDen/Settings.hs: base hostname, path and URL, home link, front page content, root directory, log files, maximum request time, maximum displayable patch/file size, database hosts/ports, etc. * the db setup required for issue trackers has been added * the register form has a security question to reduce junk signups * issue trackers can be enabled/disabled per-repo * a robots.txt file has been added (default: allow all bots) * non-content pages now have NOINDEX meta tag to discourage search indexing * user repos and log files have moved to subdirectories for easier management * a makefile has been added for developer convenience Reliability * error messages are more user-friendly * intermittent browsing errors and eventual stylesheet loss due to non-thread-safe working directory in libdarcs have been fixed * viewing a patch or file with binary data no longer gives an error * patch content larger than 200K is elided, avoiding some timeouts * viewing a patch shows the page right away and fetches the patch data asynchronously, with a more friendly message if it times out * viewing a non-existent patch id shows a 404 instead of an exception * source code highlighting is faster (using highlighting-kate); viewing a complex file (like minified jquery.js) no longer times out * the error-prone repo bootstrap feature has been dropped * patch author names are now replaced with user links reliably (when the email address matches) * repo links now work when the current url ends in / * . (period) is supported in repo names * merge now redirects properly when it completes * the login button in the issue tracker now works * private repos are now listed for their owners * private repos are no longer darcs gettable by non-owners * patch author names now link to local users and hide email addresses reliably * input fields now accept at most 1000 characters * ssh access now supports DSA public keys Usability * the site favicon now works in Chrome * the register form now disables browser autofill and is readable in Chrome * navigation buttons are clearer and more context-sensitive * the front page remains accessible after login * users are listed on the front page * repos are listed alphabetically * page headings are more consistent when browsing files * files view displays directory names in bold * when viewing file content, long lines now use all space to window edge * all markdown files are now rendered as markdown, not just README * the patches view has been renamed branches, and shows all related repos including upstream * merging patches can now also be done by repo members * pagination controls also appear at the top and have a stable layout for easy clicking * patch view lists files alphabetically * patch view now also displays added/removed file content * all issues, closed issues views have been added * code blocks on issue pages no longer overflow their background * list styles have been improved in markdown * button transition, border radius and box shadow styles have been updated for modern browsers Credits: -------- Alex Suraci created darcsden. Simon Michael led this release, with help from Ganesh Sittampalam, Guillaume Hoffmann, Niklas Haas, Daniel Patterson, Owen Stephens and Scott Lawrence. darcsden depends on Darcs, Snap, GHC, and the rest of the Haskell ecosystem. Contributing: ------------- I think darcsden fills a strategic niche in the Darcs ecosystem and deserves wider use and more active development. It has a small, clean codebase and is fun to hack on, not least because (if you contribute to hub's darcsden branch) useful changes will quickly be deployed at hub.darcs.net, providing a tight dogfooding/feedback loop. Here's how to contribute a patch there: - register at hub.darcs.net, add your ssh key in settings - fork http://hub.darcs.net/simon/darcsden - darcs get http://hub.darcs.net/yourname/darcsden - (edit, record) - darcs push yourname@hub.darcs.net:darcsden - your change appears at http://hub.darcs.net/simon/darcsden/patches ; ping me by IRC or email to merge it Best, -Simon, Alex and the Darcs team

1 1