July 2009 - Beginners

The Applicative instance for ((->) a)
by Ian Duncan 11 Jul '09

11 Jul '09

Hey folks, I understand most of what is going on with the applicative class, but I can't figure out why this instance is useful: "instance Applicative ((->) a) where..." Can anyone offer some intuition into how this is could be used? Ian Duncan

4 4

List.sort
by Patrick LeBoutillier 11 Jul '09

11 Jul '09

Hi, I see the type of the List.sort function is: Ord a => [a] -> [a] I don't understand how this type can allow it to sort pairs: Prelude> :m +List Prelude List> sort [(1, "1"), (3, "3"), (2, "2")] [(1,"1"),(2,"2"),(3,"3")] How can a pair by of type "Ord a"? Is it a rule that the first element is automatically used? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

2 1

decorate-sort-undecorate in haskell
by Ivan Uemlianin 11 Jul '09

11 Jul '09

Dear All I'm learning Haskell from a background in Python, and I'm just looking at the sort and sortBy functions in Data.List. In Python, the decorate-sort-undecorate pattern is a popular alternative to using an explicit compare function. For example, to sort a list of lists by length: def sortByLength(xs): dec_xs = [(len(x), x) for x in xs] dec_xs.sort() undec_xs = [x[1] for x in dec_xs] return undec_xs This is often preferred to something like: xs.sort(lambda x,y: len(x) > len(y)) # just used lambda so it fits on one line I think the reasoning is that plain sort() is done at C speed, whereas sort(func) is done in Python, so, depending on the list I suppose, dsu can be worth the trouble. (Sorry for vagueness). Anyway, I was wondering if dsu is popular in Haskell, and whether or when it would make sense to use dsu rather than sortBy. Here's a verbose dsu I wrote myself: sortDSU decFunc a = undecorate (sort (decorate decFunc a)) decorate decFunc [] = [] decorate decFunc (x:xs) = ( ((decFunc x), x) : decorate decFunc xs ) undecorate [] = [] undecorate ( (_, y) :xs) = ( y : undecorate xs ) Here's a terser and perhaps more idiomatic (but I think equivalent) dsu which I then found in a comment at the Real World Haskell website: dsuSort decFunc a = map snd (sort (zip (map decFunc a) a)) I have tested both functions with length and sum in ghci. So, do Haskell programmers use the decorate-sort-undecorate pattern? If not, why not? If so, when? Thanks and best wishes Ivan -- ============================================================ Ivan A. Uemlianin Speech Technology Research and Development ivan(a)llaisdy.com www.llaisdy.com llaisdy.wordpress.com www.linkedin.com/in/ivanuemlianin "Froh, froh! Wie seine Sonnen, seine Sonnen fliegen" (Schiller, Beethoven) ============================================================

4 7

Understanding State
by Geoffrey Marchant 10 Jul '09

10 Jul '09

I'm trying to understand how to use State in a function. I've avoided the topic for several years because State just never seemed very useful, but I figure it's time for me to figure it out: I have the following function > update :: (a -> (r,a)) -> Int -> [a] -> (r, [a]) > update s 0 (a:as) = let (r,a') = s a in (r,a':as) > update s i (a:as) = let (r,as') = update s (i-1) as in (r, a:as') which updates a particular element of a list. Looking at it, I see two parts of the type signature that look like State types, which leads me to think of this: > update' :: State a r -> Int -> State [a] r Which leads to me writing this: > update' s 0 = do > (a:as) <- get > let (r, a') = runState s a > put (a':as) > return r > update' s i = do > (a:as) <- get > put as > r <- update' s (i-1) > as' <- get > put (a:as') > return r Now, this just looks awful. The first half, the base condition, is actually "running" a State calculation. And the second half sets the state within the monad twice! I like the idea of using State because it simplifies the type. When I see (a -> (b,a)) I say "Wait a second, that's a State calculation, isn't it?" and then, hopefully, generalize. But I can't write that calculation nearly as concisely. How do I do this properly?

3 3

guitar tuner alike
by Bernhard Lehnert 06 Jul '09

06 Jul '09

Hi, would there, by any chance, be something like a simple and well documented way to read sound from a microphone on the soundcard and perform a fft or sth. to find the pitch of a sound? There is a whole lot of so called "guitar tuner" progs doing that, but any simple to use library for haskell? (Preferebly available on Windows, too.) Looking through hackage it seems to me that there is a wealth of libs for sound and music synthesis but not so much for sound analysis. Good online reading advice on the topic (be it haskell or not) would also be greatly appreciated (maybe some handbook for the dsp package?). Thanks, Bernhard

3 2

Help with "20 intermediate haskell exercises"
by Patrick LeBoutillier 06 Jul '09

06 Jul '09

Hi, I'm running through these Haskell exercises: http://dibblego.wordpress.com/2008/09/18/20-intermediate-haskell-exercises/ and I'm stuck at number 9: class Misty m where banana :: (a -> m b) -> m a -> m b unicorn :: a -> m a -- Exercise 9 -- Relative Difficulty: 6 instance Misty ((->) t) where banana = ??? unicorn x = (\t -> x) I can picture it when m is "[]" or "Maybe", but I can't wrap my head around the banane implementation for "((->) t)". I can see that this somewhat looks like a Monad, with unicorn = return and banana = (flip >>=) or something. Perhaps some kind of reader Monad? Can anyone offer any insight? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

3 6

Re: [Haskell-beginners] help with types and composition
by Dan Douglas 06 Jul '09

06 Jul '09

Ah silly me I think I sorta get it. after looking up currying this somewhat makes sense (it isn't really mentioned in YAHT and not till later in most other books.) So, basically any function's type will always be in curryfied form, and the only time there's a tuple involved is if the function's argument is itself a tuple? I'll have to ponder a bit how nesting functions are equivalent to a function with multiple arguments. Sorry about the messed up Unicode. That question doesn't really make sense knowing this. On 6 Jul 2009, Daniel Fischer wrote: > Am Montag 06 Juli 2009 13:53:01 schrieb Dan Douglas: > > Hello everyone! first post here. I'm working through YAHT and Real World > > Haskell sort of in parallel. I have a somewhat related question. > > > > Assume we have a binary operator which is not a higher order function. The > > "greater than" relation for example: > > > > Prelude List> :t (>) > > (>) :: forall a. (Ord a) => a -> a -> Bool > > > > Type classes and variables make sense - I assume since we have quantifiers, > > the type classes must be essentially predicates, and the type variables are > > bound to them as expected. Also I assume whenever we see (a -> b) this > > means roughly f:(<domain> -> <codomain>) > > Correct. > > > > > a -> a -> Bool could therefore mean either: "a function whose domain is an > > 'a' and whose codomain is a function from a to bool"; > > Yes, that's it. > > > or "a function which > > takes a function from type 'a' to 'a' and returns a bool. > > That would be the type (a -> a) -> Bool. > > > > > According to YAHT: > > > > "NOTE The parentheses are not necessary; in function types, if you > > have a -> b -> y it is assume that b -> y is grouped. If you want the > > other way, with a -> b grouped, you need to put parentheses around > > them." > > In short: (->) is right associative, > > a -> b -> c -> d === a -> (b -> (c -> d)) > > > > > > I'm confused by this. A function which takes multiple arguments should be > > equivalent to a predicate bound to some n-tuple. Or in this case of a > > binary infix operator, equivalent to a prefix operator which takes a tuple. > > Correct. > > > But, (a, a) is not equivalent to (a -> a), > > Indeed it isn't, the two sets don't even have the same cardinality (except a > contains only > one element). > But (a -> a) -> Bool is *not* equivalent to a -> (a -> Bool). > > > and (a -> Bool) just doesn't make sense as a range. > > But it does. (a -> Bool) is a perfectly reasonable set/Haskell type. > Functions whose result is a function are very common in functional > programming. > > > It should be something like: > > > > (>) :: forall a. (Ord a) => (a, a) -> Bool > > Note that, (ignoring _|_ and partial functions), the types ((a,b) -> c) and > (a -> (b -> c)) are isomorphic. The isomorphism is given by > > curry :: ((a,b) -> c) -> (a -> (b -> c)) > curry f = \x y -> f (x,y) > > and > > uncurry :: (a -> (b -> c)) -> ((a,b) -> c) > uncurry g = \(x,y) -> g x y > > > > > Someone on freenode told me that if you had: > > > > foo :: a -> b > > bar :: b -> c > > baz :: c -> d > > > > and: > > > > bork = (baz . bar . foo) > > > > then: > > > > bork :: a -> d > > > Yup. > > > > Which, if correct means Haskell should always chain types for first-order > > functions. And since (>) is transitive, it should satisfy > > ∀x∀y∀z(((x,y) ∈ R & (y,z) ∈ R) -> (x,z) > > ∈ R) and omit the case for (y,z). > > > ??? > > > > > How it is possible to express a function which takes multiple arguments (or > > any first-order function at all) with more than one arrow/map symbol? How > > does this even make sense? > > > > It gets even worse with more complicated examples: > > > > Prelude List> :t foldl > > foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a > > > > Prelude List> :t (>>=) > > (>>=) > > > > :: forall (m :: * -> *) a b. (Monad m) => m a -> (a -> m b) -> m b > > > > How do the non-existent associativity rules make complex function types > > seemingly without enough parentheses have unique meaning? > > The associativity rules exist: > > (->) associates to the right. > > Hence, fully parenthesised: > > foldl :: (a -> (b -> a)) -> (a -> ([b] -> a)) > > Due to the right associativity, you can omit three pairs of parentheses. > > > > > Nearly every example in every tutorial on types I can find has this > > unexplained phenomenon, or I'm really not reading carefully. > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

3 2

Re: [Haskell-beginners] help with types and composition
by Dan Douglas 06 Jul '09

06 Jul '09

Hello everyone! first post here. I'm working through YAHT and Real World Haskell sort of in parallel. I have a somewhat related question. Assume we have a binary operator which is not a higher order function. The "greater than" relation for example: Prelude List> :t (>) (>) :: forall a. (Ord a) => a -> a -> Bool Type classes and variables make sense - I assume since we have quantifiers, the type classes must be essentially predicates, and the type variables are bound to them as expected. Also I assume whenever we see (a -> b) this means roughly f:(<domain> -> <codomain>) a -> a -> Bool could therefore mean either: "a function whose domain is an 'a' and whose codomain is a function from a to bool"; or "a function which takes a function from type 'a' to 'a' and returns a bool. According to YAHT: "NOTE The parentheses are not necessary; in function types, if you have a -> b -> y it is assume that b -> y is grouped. If you want the other way, with a -> b grouped, you need to put parentheses around them." I'm confused by this. A function which takes multiple arguments should be equivalent to a predicate bound to some n-tuple. Or in this case of a binary infix operator, equivalent to a prefix operator which takes a tuple. But, (a, a) is not equivalent to (a -> a), and (a -> Bool) just doesn't make sense as a range. It should be something like: (>) :: forall a. (Ord a) => (a, a) -> Bool Someone on freenode told me that if you had: foo :: a -> b bar :: b -> c baz :: c -> d and: bork = (baz . bar . foo) then: bork :: a -> d Which, if correct means Haskell should always chain types for first-order functions. And since (>) is transitive, it should satisfy ∀x∀y∀z(((x,y) ∈ R & (y,z) ∈ R) -> (x,z) ∈ R) and omit the case for (y,z). How it is possible to express a function which takes multiple arguments (or any first-order function at all) with more than one arrow/map symbol? How does this even make sense? It gets even worse with more complicated examples: Prelude List> :t foldl foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a Prelude List> :t (>>=) (>>=) :: forall (m :: * -> *) a b. (Monad m) => m a -> (a -> m b) -> m b How do the non-existent associativity rules make complex function types seemingly without enough parentheses have unique meaning? Nearly every example in every tutorial on types I can find has this unexplained phenomenon, or I'm really not reading carefully.

2 1

When did Haskell become fun for you?
by aditya siram 05 Jul '09

05 Jul '09

Hi all, I have been pursuing Haskell for about a year now and the community has been awesome. The learning curve has been ( and is still ) steep for me because of the sheer density of the concepts, but it has changed the way I think about programming. Relating it to music, Haskell is like jazz, the concepts are heady and the entry into that world requires a high level of patience and discipline. But in the end, you want to zone out and play. How long was it before you could just play Haskell? Thanks ... -deech

1 0

Re: [Haskell-beginners] help with types and composition
by Troy Pracy 04 Jul '09

04 Jul '09

I've just started learning Haskell and I've been wondering about this issue as well. I can usually work out a point-free version by carefullty deriving it step-by-step, but I was wondering if Haskell had composition operators/functions for dealing with the various forms of composition where a 2-arg function is involved. I've played around with J (APL's successor) a little and noticed that J has various options for composing two functions (Ponit-free, or "implicit" style is very important in J). Some of the distinctions have to do with J's native array operations and aren't relevant here, but many are. Here are Haskell versions... (note: "monadic" below isn't used in the Haskell/CT sense - "monadic" and "dyadic" in J jsut refer to how many arguments an operator acts on) -- hook is the J dyadic hook as a function. hook :: (a->b->c) -> (d->b) -> a -> d -> c hook f g = \x y -> f x (g y) -- J's monadic hook mhook :: (a->b->c) -> (a->b) -> a -> c mhook f g = \x -> (hook f g) x x -- J's monadic fork fork :: (a->b->c) -> (d->a) -> (d->b) -> d -> c fork f g h = \x -> f (g x) (h x) -- J's dyadic fork dyfork :: (a->b->c) -> (d->e->a) -> (d->e->b) -> d -> e -> c dyfork f g h = \x y -> f (g x y) (h x y) -- J's dyadic @ or @: - composition of 1-arg fn with 2-arg fn compose12 :: (a->b) -> (c->d->a) -> c -> d -> b compose12 f g = \x y -> f (g x y) (@:) = compose12 {- J's dyadic & or &: - composition of 2-arg fn with 1-arg fn, resulting in a 2-arg fn (f&:g) which applies g to *both* args before passing them to f. Haskell's composition operator and partial application allow a composition of such fns (f . g) where g is applied only to the first arg. -} compose21 :: (a->a->b) -> (c->a) -> c -> c -> b compose21 f g = \x y -> f (g x) (g y) (&:) = compose21 / /I know a lot of Haskell is written in point-free style and I would have thought Haskell would have operators for some of this, but judging from the previous responses, it looks like it might not. That surprises me, since some of this seems to crop up a lot, but as I said I've just started learning Haskell, so I guess I'll have to give myself some time to absorb the Haskell way of doing things.

3 3