On Sat, Nov 21, 2009 at 05:57:45PM +0000, Philip Scott wrote:

What a fantastic and comprehensive answer, thank you!

No problem. :)

I now need to sit down and digest it. There are so many little clever tricks you can do with Haskell, is there a collection of them somewhere?

Lately people have been suggesting the Typeclassopedia[1] as a good place for begginners. It's a good reading and I recommend it, I just don't know if you'll find everything needed for my answer there. In general, however, you just need practice. Go code! =) [1] http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf

If you want to collect your obligatory cookie and are ever in and around Cambridge UK let me know :)

Too bad I'm 8837 km away from Cambridge according to Alpha =(... Cheers, -- Felipe.

On Sat, Nov 21, 2009 at 9:33 PM, Philip Scott wrote:

For the other newbies, 'second' takes a function and a tuple, it applies the function to the second thing in your tuple and returns a tuple with the first value unchanged, and the result of applying 'f' to the second:

That's what it does on a specific arrow, though generally that's the idea.

What I am struggling to understand is what on earth the type signature means:

:t second second :: (Arrow a) => a b c -> a (d, b) (d, c)

How can (\x -> "fish") be an 'a b c' when it really looks like this:

:t (\x->"fish") (\x->"fish") :: t -> [Char]

Right, but you must understand that (->) is a type constructor, just like Maybe or Either or your Ts. It takes two types parameter and return a function type. So "a -> b" is the infix syntax, but you could write that "(->) a b" just like you can write "3 + 5" as "(+) 3 5". Once you've done that on your function you get "(->) t Char" which looks a bit more like "a b c"... The final piece is that (->) is an Arrow, the most basic one but still an Arrow, so if you replace a by (->) in the type of second, you get : second :: (->) b c -> (->) (d, b) (d, c) which is just second :: (b -> c) -> (d, b) -> (d, c) which corresponds exactly to the action of second you described (that's the only function that could have this type, except bottom of course). -- Jedaï

On Sat, Nov 21, 2009 at 09:07:38PM +0000, Philip Scott wrote:

...

The final piece is that (->) is an Arrow, the most basic one but still an Arrow, so if you replace a by (->) in the type of second, you get : second :: (->) b c -> (->) (d, b) (d, c) which is just second :: (b -> c) -> (d, b) -> (d, c)

Ahh I see, very clever! There is method to the madness after all; I should never have doubted you Haskell. Thank you for taking the time to explain that :)

Do you know of any good discussions/tutorials on Arrows? I've only managed to find little snippets here and there

http://www.haskell.org/arrows/

The two tutorials linked from the "Bibliogrphy" section of that page are very good: http://www.soi.city.ac.uk/~ross/papers/fop.html http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf You may also be interested in reading the "Category" and "Arrow" sections of the Typeclassopedia: http://www.haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf -Brent

On Sat, Nov 21, 2009 at 10:13 PM, John Dorsey wrote:

Chaddaï Fouché wrote:

...

second :: (b -> c) -> (d, b) -> (d, c) which corresponds exactly to the action of second you described (that's the only function that could have this type, except bottom of course).

Nonsense!  There are several perfectly good Haskell functions with that type.  I count seven:

second :: (b -> c) -> (d, b) -> (d, c) second = Control.Arrow.second second = undefined second = const undefined second = const (const undefined) second = const (const (undefined,undefined)) second f (d,b) = (undefined, f b) second f (d,b) = (d, undefined)

Right... Let's just say functions that may be evaluated to normal form if their parameters can be evaluated to normal form. Nitpicker !! :P -- Jedaï

Daniel Fischer re-nitpicked:

I don't see

second f (d,b) = (undefined, f undefined) second f (d,b) = (d, f undefined)

in there.

Brilliant! I thought I might have missed something, hence "I count seven" instead of "there are seven". John

On Sat, Nov 21, 2009 at 08:33:28PM +0000, Philip Scott wrote:

Righto, I am getting stuck in with that. One last question; I've been trying to read up on Arrows and my mind is being boggled. Via experiment, I have worked out what 'second' was doing (the documentation is useless unless you already understand a lot of stuff I clearly don't)

For the other newbies, 'second' takes a function and a tuple, it applies the function to the second thing in your tuple and returns a tuple with the first value unchanged, and the result of applying 'f' to the second:

...

second (\x -> "fish") (10,20) (10,"fish")

What I am struggling to understand is what on earth the type signature means:

:t second second :: (Arrow a) => a b c -> a (d, b) (d, c)

How can (\x -> "fish") be an 'a b c' when it really looks like this:

:t (\x->"fish") (\x->"fish") :: t -> [Char]

And I am pretty sure I never made any Arrpws...

I feel I am on the verge of understanding something deep and fundamentally philosophical about the typesystem but I can't quite bend my mind around to it :)

The problem you're facing is that you have to think of the arrow operator (->) as a type constructor. IOW, to unify : a b c with t -> [Char] you have the following "assignments": a ~ (->) b ~ t c ~ [Char] In another other words, t -> [Char] is the same as (->) t [Char] Now it's easy to see whats happening. Note that (->) is an instance to Arrow, in GHCi: Prelude Control.Arrow> :i Arrow class (Control.Category.Category a) => Arrow a where arr :: (b -> c) -> a b c first :: a b c -> a (b, d) (c, d) second :: a b c -> a (d, b) (d, c) (***) :: a b c -> a b' c' -> a (b, b') (c, c') (&&&) :: a b c -> a b c' -> a b (c, c') -- Defined in Control.Arrow instance Arrow (->) -- Defined in Control.Arrow <<< HERE <<< instance (Monad m) => Arrow (Kleisli m) -- Defined in Control.Arrow Specializing those types to Arrow (->) and using the common infix notation we have that: arr :: (b -> c) -> (b -> c) first :: (b -> c) -> ((b, d) -> (c, d)) second :: (b -> c) -> ((d, b) -> (d, c)) (***) :: (b -> c) -> (b' -> c') -> ((b, b') -> (c, c')) (&&&) :: (b -> c) -> (b' -> c') -> (b -> (c, c')) Note that 'arr = id'. That's why we may use all Arrow functions on, err, plain functions without having wrap everything with 'arr' (as you would with any other arrow). It's a good exercise to try to reproduce the definition of the Arrow (->) instance by defining the functions above. Most definitions, if not all, are just the corresponding free theorems (meaning roughly that the definition follows from the type because that's the only definition that doesn't have undefined's). HTH! -- Felipe.

On Sun, Nov 22, 2009 at 03:32:07PM +0000, pbrowne wrote:

On Sat, Nov 21, 2009 at 21:08 Felipe Lessa wrote:

...

Most definitions, if not all, are just the corresponding free theorems (meaning roughly that the definition follows from the type because that's the only definition that doesn't have undefined's).

Question: Is it correct to paraphrase Felipe's description as follows: In Haskell the *term theorems for free* means roughly that the definition of a class, instance or a function follows from the supplied types because they are the only types that don’t have undefined argumens or undefined return types.

That is a good way to paraphrase Felipe's description --- but I don't think Felipe's terminology is correct. Many types do indeed have only a small number, or even only one, possible "interesting" implementation that does not involve undefined anywhere. However, this is not what is meant by "free theorems". A "free theorem" is a *property* which is satisfied by any function with a particular type. For example, any function with the type foo :: [a] -> Maybe a necessarily satisfies foo (map f xs) = fmap f (foo xs) (or, in points-free form, foo . map f = fmap f . foo ) for any list xs and function f, no matter what the implementation of foo (as long as it does not involve undefined or unsafePerformIO or any "cheating" of that sort). -Brent

On Sun, Nov 22, 2009 at 04:12:29PM +0000, pbrowne wrote:

On Sun, Nov 22, 2009 at 03:32:07PM +0000, Brent Yorgey wrote:

...

A "free theorem" is a *property* which is satisfied by any function with a particular type. For example, any function with the type

foo :: [a] -> Maybe a

necessarily satisfies

foo (map f xs) = fmap f (foo xs)

A theorem is a statement which has been proved on the basis of previously established theorems or axiom. So, should the definition of the function not satisfy the signature? I may be confusing terminology here. I am coming of an OBJ2/Maude/CafeOBJ background to Haskell. In CafeOBJ a *property* of an operation could, for example, be associativity. I am having difficulty in adjusting to Haskells level of formality.

I'm not quite sure what you're asking here. My point is just that a "free theorem" will be of the form "Any function f of type T, *no matter how f is implemented*, will always satisfy the following property: blah blah f blah = blah f blah " This has nothing to do with whether or not there is only one possible implementation of f that does not involve undefined, which is a different phenomenon.

...

...

In Haskell the *theorems for free* means roughly that the definition of a class, instance or a function follows from the supplied types because they are the only types that don’t have undefined argumens or undefined return types.

Question: Is my generalization of applying the "free theorem" concept to classes and instances correct?

Classes don't have types, so I'm not sure what you mean by including classes. Generalizing to instances makes sense; type class instances are just composed of a list of functions. However, again, this notion of there sometimes being only one possible implementation of a particular type has nothing to do with the concept of "free theorems". (At least, it has not much to do with it that I am aware of.)

On Nov 22, 2009, at 10:32 , pbrowne wrote:

On Sat, Nov 21, 2009 at 21:08 Felipe Lessa wrote:

...

Most definitions, if not all, are just the corresponding free theorems (meaning roughly that the definition follows from the type because that's the only definition that doesn't have undefined's).

Question: Is it correct to paraphrase Felipe's description as follows: In Haskell the *term theorems for free* means roughly that the definition of a class, instance or a function follows from the supplied types because they are the only types that don’t have undefined argumens or undefined return types.

Pretty much. It's not specific to Haskell, either; it's a result of the Curry-Howard correspondence between programs and mathematical proofs. http://homepages.inf.ed.ac.uk/wadler/papers/free/free.ps is the canonical paper on deriving free theorems from Hindley-Milner type systems. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Hi Stephan,

...

instance Num a => Num [a] where (+) = zipWith (+) (-) = zipWith (-) (*) = zipWith (*) fromInteger = repeat . fromInteger abs = map abs signum = map signum

Oooh I had no idea you could do that with 'instance' I merge my lists into a list of pairs before I do anything with them so unevenness isn't a problem; I was just trying t convince haskell that I could use nice operators like '+' on my derived type. Thank you very much for your reply; between that and Felipe's I have enough to keep me busy all evening digesting the new toys you have demonstrated :) - Philip

Philip,

I merge my lists into a list of pairs before I do anything with them so unevenness isn't a problem; I was just trying t convince haskell that I could use nice operators like '+' on my derived type.

There's another way to use nice operators like '+', in cases where the type you're using it with just doesn't make sense as an instance of Class Num. (I think there's an argument that your [(date,value)] type isn't a number and shouldn't be a Num, but I'm not going to go there.) Every module can have its own definition for each name, such as the operator (+). So in your module (eg. module Main, or module DateValueSeries), you can go ahead and define your own (+). The major caveat is making sure you don't conflict with the default (+), which lives in module Prelude, which is normally automatically brought into scope. So you could do this: -- file DateValueSeries.hs module DateValueSeries where import Prelude hiding ((+)) (+) :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)] (+) = addSkip addSkip = ... -- file main.hs import Prelude hiding ((+)) import DateValueSeries dvlist1 = [(0,100)] dvlist2 = ... dvlist3 = dvlist1 + dvlist2 The code is incomplete and untested, of course. The basic idea is that you can use (+) for something that isn't exactly addition (although you're choosing that name because it's clearly related to addition). Unlike the examples using Class Num your (+) has nothing to do with the normal (+); it just has the same name. John

Philip Scott wrote:

Thanks John,

...

Every module can have its own definition for each name, such as the operator (+). So in your module (eg. module Main, or module DateValueSeries), you can go ahead and define your own (+). The major caveat is making sure you don't conflict with the default (+), which lives in module Prelude, which is normally automatically brought into scope.

That actually quite nicely solves the problem... it feels almost a little too easy, after spending the evening getting my mind wrapped up with Arrows :)

why has no one mentioned: you most likely don't need to understand Arrows? I'm pretty good with Haskell, and Arrows are still somewhat confusing to me. Why? Most problems I've worked with in Haskell have had more-idiomatic solutions than Arrows. (examples include: Monad; Functor; Applicative; just plain functions; plain old lack of type-class abstraction.) It's not so easy or useful to understand any abstraction/class without using at least two or three useful examples/instances of it first. -Isaac

If you don't yet understand Arrows, then what compels you to conclude that there are more idiomatic solutions (than what you don't yet understand)? Just sayin' Isaac Dupree wrote:

Philip Scott wrote:

...

Thanks John,

...

Every module can have its own definition for each name, such as the operator (+). So in your module (eg. module Main, or module DateValueSeries), you can go ahead and define your own (+). The major caveat is making sure you don't conflict with the default (+), which lives in module Prelude, which is normally automatically brought into scope.

That actually quite nicely solves the problem... it feels almost a little too easy, after spending the evening getting my mind wrapped up with Arrows :)

why has no one mentioned: you most likely don't need to understand Arrows? I'm pretty good with Haskell, and Arrows are still somewhat confusing to me. Why? Most problems I've worked with in Haskell have had more-idiomatic solutions than Arrows. (examples include: Monad; Functor; Applicative; just plain functions; plain old lack of type-class abstraction.) It's not so easy or useful to understand any abstraction/class without using at least two or three useful examples/instances of it first.

-Isaac _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Tony Morris http://tmorris.net/

2009/11/22 Isaac Dupree :

Sorry to take offense :-) maybe I was being too modest?

It seems Arrows are a necessary abstraction for a couple very particular world-views/paradigms, and don't fit very well with a lot of other stuff.

Hello All I wouldn't go quite as far as saying Arrows are misfits, but in Isaac's defence, if all you have are pure functions, then arrows are just a wee bit, erm, boring. In Philip's original message he happened to be representing his data as a pair, so second worked fine as a projection/application function, vis: *Arrows> second (\x -> "fish") (10,20) (10,"fish") But of course it doesn't work as a projection/application function for triples (sorry I lack a better term for projection/application): *Arrows> second (\x -> "chips") (10,20,30) <interactive>:1:0: Couldn't match expected type `(t, t1, t2)' against inferred type `(d, b)' In the expression: second (\ x -> "chips") (10, 20, 30) In the definition of `it': it = second (\ x -> "chips") (10, 20, 30) Nor would it work if Philip had defined his own data type. Also for pure functions the derived operators (>>^) and (^>>) become (.), and (<<^) & (^<<) are become reverse composition - which was sometimes called (##) but now seems categorized as (<<<) . The code below is a bit superfluous to the discussion, but it does define the arrow operations for pure functions with the type constructor simplified to (->), I occasionally do the Arrow combinators longhand when I can't remember which Arrow combinator does what. Best wishes Stephen

module ArrowLonghand where

import Control.Arrow

arr :: (b -> c) -> a b c fun_arr :: a b c -> (b -> c) where a = (->)

fun_arr :: (b -> c) -> (b -> c) fun_arr f = f

arr's definition is clearly identity, but specialized to functions

alt_fun_arr :: (b -> c) -> (b -> c) alt_fun_arr = id

first :: a b c -> a (b, d) (c, d) fun_first :: a b c -> a (b,d) (c,d) where a = (->)

fun_first :: (b -> c) -> (b,d) -> (c,d) fun_first f (x,y) = (f x, y)

second :: a b c -> a (d, b) (d, c) fun_second :: a b c -> a (d,b) (d,c) where a = (->)

fun_second :: (b -> c) -> (d,b) -> (d,c) fun_second f (x,y) = (x, f y)

(***) :: a b c -> a b' c' -> a (b, b') (c, c') fun_starstarstar :: a b c -> a b' c' -> a (b,b') (c,c') where a = (->)

fun_starstarstar :: (b -> c) -> (b' -> c') -> (b,b') -> (c,c') fun_starstarstar f g (x,y) = (f x, g y)

Funnily enough, (***) is not unlike prod from Jeremy Gibbons 'Pair Calculus': http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/acmmpc-calc...

prod :: (b -> c) -> (b' -> c') -> (b,b') -> (c,c') prod f g = fork (f . fst, g . snd)

(&&&) :: a b c -> a b c' -> a b (c, c') fun_ampampamp :: a b c -> a b c' -> a b (c,c') where a = (->)

fun_ampampamp :: (b -> c) -> (b -> c') -> b -> (c,c') fun_ampampamp f g x = (f x, g x)

Funnily enough, (&&&) is not unlike fork from the Pair Calculus...

fork :: (b -> c, b -> c') -> b -> (c,c') fork (f,g) a = (f a, g a)

pair_first :: (b -> c) -> (b,d) -> (c,d) pair_first f = f `prod` id

pair_second :: (b -> c) -> (d,b) -> (d,c) pair_second g = id `prod` g

-------------------------------------------------------------------------------- (^>>) :: Arrow a => (b -> c) -> a c d -> a b d

preCompLR :: (b -> c) -> (c -> d) -> (b -> d) preCompLR f g = \x -> g (f x)

(>>^) :: Arrow a => a b c -> (c -> d) -> a b d

postCompLR :: (b -> c) -> (c -> d) -> (b -> d) postCompLR f g = \x -> g (f x)

(^>>) and (>>^) are the same for functions. -- reverse (<<^) :: Arrow a => a c d -> (b -> c) -> a b d

preCompRL :: (c -> d) -> (b -> c) -> (b -> d) preCompRL f g = \x -> f (g x)

(^<<) :: Arrow a => (c -> d) -> a b c -> a b d

postCompRL :: (c -> d) -> (b -> c) -> (b -> d) postCompRL f g = \x -> f (g x)