- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] generalizing the writer monad
by Strake 24 Oct '12

24 Oct '12

On 17/10/2012, Petr P <petr.mvd(a)gmail.com> wrote: > Hi, > > (this is a literate Haskell post.) > > lately I was playing with the Writer monad and it seems to me that it > is too tightly coupled with monoids. Currently, MonadWriter makes the > following assumptions: > > (1) The written value can be read again later. > (2) For that to be possible it has to be monoid so that multiple (or > zero) values can be combined. > > I fell say that this is a bit restricting. Sometimes, the written > value can be lost - either used to compute something else or for > example sent out using some IO action to a file, network etc. For > example, I'd like to create an IO-based writer monad whose `tell` logs > its argument somewhere - prints it, stores to a file etc. No need: newtype SequenceM m a = SequenceM (m a); instance (Monad m, Monoid a) => Monoid (SequenceM m a) where { mempty = SequenceM (return mempty); SequenceM mx `mappend` SequenceM my = SequenceM (liftM2 mappend mx my); } whatever :: (MonadWriter (SequenceM IO ()) m) => m (); whatever = tell (SequenceM (someIO :: IO ())); Cheers, Strake

2 1

Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
by John Lato 24 Oct '12

24 Oct '12

> From: Alfredo Di Napoli <alfredo.dinapoli(a)gmail.com> > Subject: [Haskell-cafe] A clarification about what happens under the > hood with foldMap > > I'm sure I'm missing a point, but the "minimum" definition for a Foldable > instance is given in terms of foldMap, so I get the cake for free, foldr > included, right? > In the example I have defined my treeSum as: > > treeSum = Data.Foldable.foldr (+) 0 > > So the only thing Haskell knows it that I want to fold over a Foldable for > which foldMap (and therefore foldr) is defined, and specifically I want to > fold using (+) as function. > But foldMap is defined in terms of f, which in this case is Sum, because I > want to sum things. It it were (*) f would have been Product, right? > > So what I'm missing is the relation between foldMap and foldr, aka "How > Haskell infer from (+) that I want f = Sum and not something different"? What you're missing is that this isn't how foldr is defined. As you probably suspect, it isn't possible for Haskell to deduce "f = Sum" from just the function. And in general the function parameter to foldr isn't even equivalent to mappend for any monoid, because it operates on two values with different types. Rather, foldr is defined using the Endo monoid, which is > newtype Endo a = Endo (a -> a) instance Monoid (Endo a) where mempty = id mappend = (.) Here's the default instance of Data.Foldable.foldr > foldr :: (a -> b -> b) -> b -> t a -> b > foldr f z t = appEndo (foldMap (Endo . f) t) z What happens is that, as the tree is traversed, Leaf constructors are replaced with 'id' (mempty :: Endo b), and branch values are replaced with 'Endo . f', where f = (+) in this example. Look at Endo . f: -- Endo :: (b -> b) -> Endo b -- f :: a -> (b -> b) -- Endo . f :: a -> Endo b so at each branch (Endo . f) is applied to the value, resulting in the type 'Endo b' foldMap just composes everything together with mappend, which, after the Endo constructor is removed, is a giant function pipeline :: b -> b, which is then applied to the provided base value (0 here). John L.

2 1

Hackage Package Discoverability
by Myles C. Maxfield 23 Oct '12

23 Oct '12

Hello, I am the author/maintainer of the 'punycode' hackage package. After 4 months, I just found that punycode conversion already exists in the Data.Encoding.BootString package inside the 'encoding' package. I'd like to deprecate my package in favor of the 'encoding' package. However, I would also like to solve the discoverability problem of people not knowing to look in the 'encoding' package when they're looking for the punycode algorithm. (I certainly didn't look there, and as a result, I re-implemented the algorithm). My initial thought is to keep my package in the hackage database, but put a big label on it saying "DEPRECATED: Use Data.Encoding.BootString instead." Is there a better way to make this algorithm discoverable? Thanks, Myles

3 3

Haskell job opening at Functor AB
by Alp Mestanogullari 23 Oct '12

23 Oct '12

Hello -cafe, There's a very cool Haskell job opening at Functor AB, involving some cool type theory, for use in nuclear fusion research. You can read about it here: http://alpmestan.com/posts/2012-10-23-haskell-job-opening-at-functor.html -- Alp Mestanogullari

1 0

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

23 Oct '12

---------- Forwarded message ---------- From: Alfredo Di Napoli <alfredo.dinapoli(a)gmail.com> Date: 23 October 2012 10:35 Subject: Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap To: Chaddaï Fouché <chaddai.fouche(a)gmail.com> I'm sure I'm missing a point, but the "minimum" definition for a Foldable instance is given in terms of foldMap, so I get the cake for free, foldr included, right? In the example I have defined my treeSum as: treeSum = Data.Foldable.foldr (+) 0 So the only thing Haskell knows it that I want to fold over a Foldable for which foldMap (and therefore foldr) is defined, and specifically I want to fold using (+) as function. But foldMap is defined in terms of f, which in this case is Sum, because I want to sum things. It it were (*) f would have been Product, right? So what I'm missing is the relation between foldMap and foldr, aka "How Haskell infer from (+) that I want f = Sum and not something different"? I hope to have been clearer, don't know if I'm missing something crucial, though :) Thanks, A.

2 2

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 23 Oct '12

23 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