- Haskell-Cafe - Haskell.org

A clarification about what happens under the hood with foldMap
by oleg＠okmij.org 23 Oct '12

23 Oct '12

> I was playing with the classic example of a Foldable structure: Trees. > So the code you can find both on Haskell Wiki and LYAH is the following: > > data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq) > > instance Foldable Tree where > foldMap f Empty = mempty > foldMap f (Node l p r) = foldMap f l `mappend` f p `mappend` foldMap f r > > treeSum :: Tree Int -> Int > treeSum = Data.Foldable.foldr (+) 0 > > > What this code does is straighforward. I was struck from the following > sentences in LYAH: > > Notice that we didn't have to provide the function that takes a value and > > returns a monoid value. > > We receive that function as a parameter to foldMap and all we have to > > decide is where to apply > > that function and how to join up the resulting monoids from it. > > This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a > Monoid. > What I was wondering about is how Haskell knows that it has to pass, for > example, Sum in case of (+) and Product in case of (*)? Hopefully the following paradox helps: > treeDiff :: Tree Int -> Int > treeDiff = Data.Foldable.foldr (-) 0 > > t1 = treeDiff (Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)) This works just as well. You might be surprised: after all, there is no Diff monoid that corresponds to (-). In fact, there cannot be since (-) is not associative. And yet treeDiff type checks and even produces some integer when applied to a tree. What gives?

1 0

Why Kleisli composition is not in the Monad signature?
by oleg＠okmij.org 23 Oct '12

23 Oct '12

Andreas Abel wrote: > I tell them that monads are for sequencing effects; and the > sequencing is visible clearly in > > (>>) :: IO a -> IO b -> IO b > (>>=) :: IO a -> (a -> IO b) -> IO b > > but not in > > fmap :: (a -> b) -> IO a -> IO b > join :: IO (IO a) -> IO a Indeed! I'd like to point out an old academic paper that was written exactly on the subject at hand: how Category Theory monads relate to monads in Haskell. Here is the relevant quotation: Monads are typically equated with single-threadedness, and are therefore used as a technique for incorporating imperative features into a purely functional language. Category theory monads have little to do with single-threadedness; it is the sequencing imposed by composition that ensures single-threadedness. In a Wadler-ised monad this is a consequence of bundling the Kleisli star and flipped compose into the bind operator. There is nothing new in this connection. Peter Landin in his Algol 60 used functional composition to model semi-colon. Semi-colon can be thought of as a state transforming operator that threads the state of the machine throughout a program. The work of Peyton-Jones and Wadler has turned full circle back to Landin's earlier work as their use of Moggi's sequencing monad enables real side-effects to be incorporated into monad operations such as print. Quoted from: Sec 3: An historical aside Jonathan M. D. Hill and Keith Clarke: An Introduction to Category Theory, Category Theory Monads, and Their Relationship to Functional Programming. 1994. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497 I'd like to stress: the single-threadedness, the trick that lets us embed imperative language into a pure one, has *little to do* with category-theoretic monads with their Klesli star. The web page http://okmij.org/ftp/Computation/IO-monad-history.html describes the work of Landin in detail, contrasting Landin's and Peyton-Jones' papers.

1 0

A clarification about what happens under the hood with foldMap
by Alfredo Di Napoli 23 Oct '12

23 Oct '12

Hi Cafe, I was playing with the classic example of a Foldable structure: Trees. So the code you can find both on Haskell Wiki and LYAH is the following: data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq) instance Foldable Tree where foldMap f Empty = mempty foldMap f (Node l p r) = foldMap f l `mappend` f p `mappend` foldMap f r treeSum :: Tree Int -> Int treeSum = Data.Foldable.foldr (+) 0 What this code does is straighforward. I was struck from the following sentences in LYAH: Notice that we didn't have to provide the function that takes a value and > returns a monoid value. > We receive that function as a parameter to foldMap and all we have to > decide is where to apply > that function and how to join up the resulting monoids from it. This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a Monoid. What I was wondering about is how Haskell knows that it has to pass, for example, Sum in case of (+) and Product in case of (*)? In other term, I'm missing the logical piece of the puzzle which maps the associative binary function passed to fold up to our foldMap declaration. Thanks for any explanation :) Cheers, A.

2 1

A yet another question about subtyping and heterogeneous collections
by oleg＠okmij.org 23 Oct '12

23 Oct '12

First of all, MigMit has probably suggested the parameterization of Like by the constraint, something like the following: data Like ctx = forall a. (ctx a, Typeable a) => Like a instance ALike (Like ALike) where toA (Like x) = toA x instance CLike (Like CLike) where toC (Like x) = toC x get_mono :: Typeable b => [Like ALike] -> [b] get_mono = catMaybes . map ((\(Like x) -> cast x)) lst_a :: [Like ALike] lst_a = [Like a1, Like b1, Like c1, Like d1] lst_c :: [Like CLike] lst_c = [Like c1, Like d1] t1 = map print_a lst_a t2 = map print_a lst_c (The rest of the code is the same as in your first message). You need the flag ConstraintKinds. Second, all your examples so far used structural subtyping (objects with the same fields have the same type) rather than nominal subtyping of C++ (distinct classes have distinct types even if they have the same fields; the subtyping must be declared in the class declaration). For the structural subtyping, upcasts and downcasts can be done mostly automatically. See the OOHaskell paper or the code http://code.haskell.org/OOHaskell (see the files in the samples directory).

2 2

Fast parsing of unboxed values without boxing them in the parser?
by Eugene Kirpichov 22 Oct '12

22 Oct '12

Hi cafe, Are there any libraries that can be used for very fast parsing of binary data into structures with unboxed fields? The "naive" way, as implemented in Data.Binary etc, has the parsing monad datatype (say, "Get a") be parametric in "a" and include a field of type "a", which makes it impossible for a parser to return an unboxed value (e.g. parse a word32 from a byte array). I'm thinking that a CPS-style parser type could allow returning an unboxed value as a result of the compiler inlining and fusing together the parsing code and the code that consumes the parsed value. Are there any libraries that work like this? -- Eugene Kirpichov http://www.linkedin.com/in/eugenekirpichov We're hiring! http://tinyurl.com/mirantis-openstack-engineer

2 1

A yet another question about subtyping and heterogeneous collections
by Dmitry Vyal 22 Oct '12

22 Oct '12

Hello list! I've been experimenting with emulating subtyping and heterogeneous collections in Haskell. I need this to parse a binary representation of objects of a class hierarchy in C++ program. So far I implemented upcasting using a chain of type classes and now I'm playing with heterogeneous lists. For future purposes It would be ideal to be able to have something like these functions: upcast_list :: [LikeC] -> [LikeA] downcast_list :: [LikeA] -> [LikeC] First one only replaces the existential wrapper leaving the actual value intact, and the second one also filters the list, passing the elements with specific enough type. I can implement this particular functions, but what's about a more general one? Something like cast_list :: [a] -> [b], where a and b are existential types from one hierarchy. Something like LikeA and LikeC in my example. Is my approach feasible? Is there a better one? Am I missing something obvious? Any relevant advices are welcome. The example code follows: {-# LANGUAGE FlexibleInstances, UndecidableInstances, OverlappingInstances, ExistentialQuantification, DeriveDataTypeable #-} import Data.Typeable import Data.Maybe data A = A {a_x :: Int} deriving (Show, Typeable) data B = B {b_x :: Int, b_a :: A} deriving (Show, Typeable) data C = C {c_z :: Int, c_b :: B} deriving (Show, Typeable) data D = D {d_w :: Int, d_c :: C, d_a :: A} deriving (Show, Typeable) class ALike x where toA :: x -> A class BLike x where toB :: x -> B class CLike x where toC :: x -> C class DLike x where toD :: x -> D instance ALike A where toA = id instance BLike B where toB = id instance CLike C where toC = id instance DLike D where toD = id instance ALike B where toA = b_a instance BLike C where toB = c_b instance CLike D where toC = d_c instance (BLike x) => (ALike x) where toA = (toA :: B -> A) . toB instance CLike x => BLike x where toB = toB . toC a1 = A 1 b1 = B 2 (A 2) c1 = C 3 b1 d1 = D 4 c1 (A 10) print_a :: ALike x => x -> String print_a v = "A = " ++ show (a_x $ toA v) sum_a :: (ALike x, ALike y) => x -> y -> String sum_a v1 v2 = "A1 = " ++ show (a_x $ toA v1) ++ " A2 = " ++ show (a_x $ toA v2) data LikeA = forall a. (ALike a, Typeable a) => LikeA a instance ALike LikeA where toA (LikeA x) = toA x get_mono :: Typeable b => [LikeA] -> [b] get_mono = catMaybes . map ((\(LikeA x) -> cast x)) data LikeC = forall c. (CLike c, Typeable c) => LikeC c instance CLike LikeC where toC (LikeC x) = toC x lst_a = [LikeA a1, LikeA b1, LikeA c1, LikeA d1] lst_c = [LikeC c1, LikeC d1]

4 6

Re: [Haskell-cafe] Blocking IO & FIFOs
by Jason Dusek 22 Oct '12

22 Oct '12

2012/10/20 Asten, W.G.G. van (Wilfried, Student M-CSC) <w.g.g.vanasten(a)student.utwente.nl>: > Would you be happy with a solution like this: > > - First create two handles to two files in the tmp directory > - Then use StdStream's UseHandle to redirect std_err and std_out > (using CreatePipe for std_in) to these files > - Then write your query to the Handle for std_in > - waitForProcess > - Collect std_out and std_err from the temporary files. > > If that is not satisfactory you may want to check out conduit-process > (http://hackage.haskell.org/packages/archive/process-conduit/0.5.0.2/doc/htm…) > that also does some interaction with a process and interleaves std_in > and std_out. It should not be to hard to combine std_err into that > concept. I also faced this same problem and in one case solved it by > using a temporary file to hold my content which was also deleted > afterwards (This immediately prevented the content building up in > memory). For my application, it's important to be able to run multiple queries against the same Bash session. Waiting for Bash to shut down is thus not a viable way to finalize the response. Perhaps I can spawn two cats with their outputs connected to the FIFOs and wait for them to terminate. -- Jason Dusek pgp // solidsnack // C1EBC57DC55144F35460C8DF1FD4C6C1FED18A2B

4 8

Oxford Haskell Users Group
by Nicolas Wu 22 Oct '12

22 Oct '12

Dear all, After a long pause over the summer, the Oxford Haskell Users Group will be meeting this week, at 8pm on Friday 26th October, at the Mitre pub on High Street, Oxford [1]. The group meets in an informal setting with no real agenda: typically we turn up, have a few pints, and enjoy a good chat about what we've been doing with Haskell. If you'd like to have more details about our meetings, then join our mailing list [2], where our meetings are usually announced. The format of OxHUG will be changing slightly: we'll be meeting once a month rather than fortnightly, and rotating the day of the week. The full details of the meetings can be found on the OxHUG calendar [3], though at the moment only this week's meeting is planned. Nick [1]: http://goo.gl/maps/QEN3o [2]: https://groups.google.com/group/oxhug [3]: https://www.google.com/calendar/embed?src=pjc31qnpq48rvvncq72utqtang%40grou…

1 0

Solving integer equations in Haskell
by Justin Paston-Cooper 21 Oct '12

21 Oct '12

Hello, Can anyone suggest a library written in Haskell which can solve equations of the form xM(transpose(x)) = y, where x should be an integer vector, M is an integer matrix and y is an integer? I'm aware that Mathematica can do this, but I would like something written in Haskell. I haven't been sure of what exact keywords I should be searching for, hence my asking here. Thanks, Justin

5 6

ANN: hledger 0.19
by Simon Michael 21 Oct '12

21 Oct '12

I'm pleased to announce the release of hledger 0.19! This release has just two visible changes: a much faster balance command, and support for the latest GHC and libs. (A hledger-web update will follow.) hledger is a command-line tool and haskell library for tracking financial transactions, which are stored in a human-readable plain text format. In addition to reporting, it can also help you record new transactions, or convert CSV data from your bank. Add-on packages include hledger-web, a web interface. hledger is inspired by and compatible with John Wiegley's Ledger. For more, see http://hledger.org . Install it: cabal update; cabal install hledger . For installation help, see http://hledger.org/MANUAL.html#installing . Or, sponsor a ready-to-run binary for your platform: http://hledger.org/DOWNLOAD.html . Release notes: hledger, hledger-lib: support GHC 7.6 and latest cmdargs, haskeline, split balance report no longer has an O(n^2) slowdown with large numbers of accounts, and is generally more speedy. Benchmark on a 2010 macbook: +-------------------------------------------++--------------+--------------+--------+ | || hledger-0.18 | hledger-0.19 | ledger | +===========================================++==============+==============+========+ | -f data/100x100x10.journal balance || 0.21 | 0.07 | 0.09 | | -f data/1000x1000x10.journal balance || 10.13 | 0.47 | 0.62 | | -f data/1000x10000x10.journal balance || 40.67 | 0.67 | 1.01 | | -f data/10000x1000x10.journal balance || 15.01 | 3.22 | 2.36 | | -f data/10000x1000x10.journal balance aa || 4.77 | 4.40 | 2.33 | +-------------------------------------------++--------------+--------------+--------+ build version is set with CPP instead of cabal-file-th Release contributors: Simon Michael, Sergei Trofimovich Release stats: 106 days, 21 commits, 1 end-user fix, 0 end-user features since last release Project stats: 222 unit & functional tests, 7740 lines of code including hledger-web, 21 committers

1 0