Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: Maybe a and Maybe t (Ivan Uemlianin) 2. Re: Maybe a and Maybe t (Daniel Fischer) 3. A try on a bank machine algorithm... (Bernhard Lehnert) 4. Re: Maybe a and Maybe t (Brent Yorgey) 5. Re: A try on a bank machine algorithm... (Alexander Dunlap) 6. Re: Maybe a and Maybe t (Ivan Uemlianin) 7. Re: A try on a bank machine algorithm... (Thomas Friedrich) 8. Re: A try on a bank machine algorithm... (Brent Yorgey) ---------------------------------------------------------------------- Message: 1 Date: Sun, 31 May 2009 14:37:27 +0100 From: Ivan Uemlianin <i...@llaisdy.com> Subject: Re: [Haskell-beginners] Maybe a and Maybe t Cc: beginners@haskell.org Message-ID: <4a228817.2060...@llaisdy.com> Content-Type: text/plain; charset=UTF-8; format=flowed Dear Andrew and Lee Thanks for your comments. Andrew Wagner wrote: > As for why it actually happens in this case, it's no doubt related to > the particular algorithm ghci uses to do the type inference. Interesting. I tried it in hugs and it doesn't happen: Main> :type safeSecond safeSecond :: [a] -> Maybe a Main> :type tidySecond tidySecond :: [a] -> Maybe a Main> So, it's a property of the ghci interpreter rather than of the language itself. Just out of curiousity, I'd be interested to know what's going on in ghci to produce this effect. Are there different types of type variable? Learning Haskell is reminding me of things I studied when I was an undergrad (linguistics)--- pattern matching in Prolog; the type system reminds me of categorial grammar; we looked at lamda calculus as part of formal semantics. So I'd like to look into this more deeply, if anyone can give me a pointer into the ghci docs. Thanks again Ivan -- ============================================================ Ivan A. Uemlianin Speech Technology Research and Development i...@llaisdy.com www.llaisdy.com llaisdy.wordpress.com www.linkedin.com/in/ivanuemlianin "Froh, froh! Wie seine Sonnen, seine Sonnen fliegen" (Schiller, Beethoven) ============================================================ ------------------------------ Message: 2 Date: Sun, 31 May 2009 17:42:44 +0200 From: Daniel Fischer <daniel.is.fisc...@web.de> Subject: Re: [Haskell-beginners] Maybe a and Maybe t To: beginners@haskell.org Message-ID: <200905311742.45381.daniel.is.fisc...@web.de> Content-Type: text/plain; charset="utf-8" Am Sonntag 31 Mai 2009 15:37:27 schrieb Ivan Uemlianin: > Dear Andrew and Lee > > Thanks for your comments. > > Andrew Wagner wrote: > > As for why it actually happens in this case, it's no doubt related to > > the particular algorithm ghci uses to do the type inference. In particular the part where GHC assigns names to type variables. > > Interesting. I tried it in hugs and it doesn't happen: > > Main> :type safeSecond > safeSecond :: [a] -> Maybe a > Main> :type tidySecond > tidySecond :: [a] -> Maybe a > Main> > > So, it's a property of the ghci interpreter rather than of the language > itself. Yes. > > Just out of curiousity, I'd be interested to know what's going on in > ghci to produce this effect. Are there different types of type variable? There are type variables of different *kind*, e.g. in class Functor f where fmap :: (a -> b) -> f a -> f b a and b are type variables of kind * (the kind of ordinary types) and f is a type variable of kind (* -> *) (the kind of type constructors which take an ordinary type and produce another ordinary type, examples are [] and Maybe). But that has nothing to do with the phenomenon, in the inferred type signatures of safeSecond and tidySecond, the 'a' resp. 't' are both type variables of kind *. The only difference is that in one case the name supply delivered 'a' and in the other it delivered 't'. ------------------------------ Message: 3 Date: Sun, 31 May 2009 23:19:02 +0200 From: Bernhard Lehnert <b.lehn...@gmx.de> Subject: [Haskell-beginners] A try on a bank machine algorithm... To: beginners <beginners@haskell.org> Message-ID: <1243804742.10638.2.ca...@sol> Content-Type: text/plain Hi, in a Python Forum someone came up with his homework. Just beginning to learn Haskell I thougt I give it a try. I came up with a working function that I present here to ask you, if I am doing this right or how I could do better. The job was: A cash machine has to compute the division of bank notes for any given amount of money. According to German wikipedia a common algorithm is to start giving one 5$ bill, one 10$ and so on as long as possible (I call this uphill). After that the maximum possible amount of large bank notes is given... Thus every customer gets some small bills and still the number of bills is limited. My answer is a function called 'paymixture' which first calls a function 'uphill' and afterwards a function 'downhill', each of which realizes one part of the above mentioned algorithm. The downhill function might also be usefull apart from the rest which is why indentation ist different... Thanks a lot, Bernhard ------------------------------------------------------------- paymixture :: (Ord t, Num t)=> t->[t]->[t] -- usage: paymixture (sum to pay) (list of possible bills) -- list of bills has to be sorted, like in -- 'paymixture 175 [5,10,20,50,100]' -- last element of the returned list is what could not be paid. paymixture n list = init(up) ++ down where up = uphill n list down = downhill (last(up)) (reverse list) uphill :: (Ord t, Num t)=> t->[t]->[t] uphill n [] = [n] uphill 0 _ = [0] uphill n (x:xs) = if n>=x then x : uphill (n-x) xs else uphill n xs downhill :: (Ord t, Num t)=> t ->[t]->[t] -- usage: downhill (sum to pay) (list of possible bills) -- list if bills has to be reverse sorted, like e. g. -- 'downhill 175 [200, 100, 50, 20, 10,5]' -- last elemt of return value is the rest that could -- not be paid. downhill n supply | (n<last supply) = [n] | otherwise = max : downhill (n-max) supply where max = head([x|x<-supply, x<=n]) ------------------------------ Message: 4 Date: Sun, 31 May 2009 20:10:34 -0400 From: Brent Yorgey <byor...@seas.upenn.edu> Subject: Re: [Haskell-beginners] Maybe a and Maybe t To: beginners@haskell.org Message-ID: <20090601001034.ga18...@seas.upenn.edu> Content-Type: text/plain; charset=us-ascii On Sun, May 31, 2009 at 05:42:44PM +0200, Daniel Fischer wrote: > > But that has nothing to do with the phenomenon, in the inferred type > signatures of > safeSecond and tidySecond, the 'a' resp. 't' are both type variables of kind > *. > The only difference is that in one case the name supply delivered 'a' and in > the other it > delivered 't'. I think one source of difference is that ghci tries to maintain type variable names from declared type signatures. So perhaps one of the library functions used to define 'safeSecond' has an explicitly declared type signature that mentions 'a', and a library function used to defined 'tidySecond' has one that mentions 't'. -Brent ------------------------------ Message: 5 Date: Sun, 31 May 2009 20:39:53 -0700 From: Alexander Dunlap <alexander.dun...@gmail.com> Subject: Re: [Haskell-beginners] A try on a bank machine algorithm... To: Bernhard Lehnert <b.lehn...@gmx.de> Cc: beginners <beginners@haskell.org> Message-ID: <57526e770905312039r720e2c17y671293ec0f06e...@mail.gmail.com> Content-Type: text/plain; charset=UTF-8 On Sun, May 31, 2009 at 2:19 PM, Bernhard Lehnert <b.lehn...@gmx.de> wrote: > Hi, > > in a Python Forum someone came up with his homework. Just beginning to > learn Haskell I thougt I give it a try. I came up with a working > function that I present here to ask you, if I am doing this right or how > I could do better. > > The job was: A cash machine has to compute the division of bank notes > for any given amount of money. > According to German wikipedia a common algorithm is to start giving one > 5$ bill, one 10$ and so on as long as possible (I call this uphill). > After that the maximum possible amount of large bank notes is given... > > Thus every customer gets some small bills and still the number of bills > is limited. My answer is a function called 'paymixture' which first > calls a function 'uphill' and afterwards a function 'downhill', each of > which realizes one part of the above mentioned algorithm. The downhill > function might also be usefull apart from the rest which is why > indentation ist different... > > Thanks a lot, > Bernhard > ------------------------------------------------------------- > paymixture :: (Ord t, Num t)=> t->[t]->[t] > -- usage: paymixture (sum to pay) (list of possible bills) > -- list of bills has to be sorted, like in > -- 'paymixture 175 [5,10,20,50,100]' > -- last element of the returned list is what could not be paid. > > paymixture n list = init(up) ++ down >    where >    up = uphill n list >    down = downhill (last(up)) (reverse list) > >    uphill :: (Ord t, Num t)=> t->[t]->[t] >    uphill n [] = [n] >    uphill 0 _  = [0] >    uphill n (x:xs) = if n>=x then x : uphill (n-x) xs >               else uphill n xs > > downhill :: (Ord t, Num t)=> t ->[t]->[t] > -- usage: downhill (sum to pay) (list of possible bills) > -- list if bills has to be reverse sorted, like e. g. > -- 'downhill 175 [200, 100, 50, 20, 10,5]' > -- last elemt of return value is the rest that could > -- not be paid. > > downhill n supply | (n<last supply) = [n] >          | otherwise = max : downhill (n-max) supply >           where max = head([x|x<-supply, x<=n]) > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > Some comments on things that would be done differently by someone with more experience: - You have more parentheses than you need. If you have head xs, it doesn't need to be head(xs). Parentheses are only needed when you want it to associate in the other direction (i.e. you need them for head (tail xs) but not take 3 xs because 3 and xs are both arguments of take but (tail xs) is one argument of head. It's actually even more complicated than that when you get into currying (although it makes a lot more sense then) but that's the simple way of thinking about it. - The "last" function is terribly inefficient - it has to traverse the entire list to get to the end. It would be better for uphill to return a pair of (all-but-last-element,last-element) because then the list wouldn't have to be traversed again to get the last element. It looks like you're doing well; good luck learning Haskell! Alex ------------------------------ Message: 6 Date: Mon, 01 Jun 2009 13:47:19 +0100 From: Ivan Uemlianin <i...@llaisdy.com> Subject: Re: [Haskell-beginners] Maybe a and Maybe t To: beginners@haskell.org Message-ID: <4a23cdd7.3080...@llaisdy.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Brent Yorgey wrote: > On Sun, May 31, 2009 at 05:42:44PM +0200, Daniel Fischer wrote: > >> But that has nothing to do with the phenomenon, in the inferred type >> signatures of >> safeSecond and tidySecond, the 'a' resp. 't' are both type variables of kind >> *. >> The only difference is that in one case the name supply delivered 'a' and in >> the other it >> delivered 't'. >> > > I think one source of difference is that ghci tries to maintain type > variable names from declared type signatures. So perhaps one of the > library functions used to define 'safeSecond' has an explicitly > declared type signature that mentions 'a', and a library function used > to defined 'tidySecond' has one that mentions 't'. > This sounds like a good answer. Thanks! I tried this: safe xs = head xs has inferred type safe :: [a] -> a tidy (x:_) = x has inferred type tidy :: [t] -> t I can rest easy now, and get on to the next exercise. Best Ivan -- ============================================================ Ivan A. Uemlianin Speech Technology Research and Development i...@llaisdy.com www.llaisdy.com llaisdy.wordpress.com www.linkedin.com/in/ivanuemlianin "Froh, froh! Wie seine Sonnen, seine Sonnen fliegen" (Schiller, Beethoven) ============================================================ ------------------------------ Message: 7 Date: Mon, 01 Jun 2009 10:55:30 -0400 From: Thomas Friedrich <i...@suud.de> Subject: Re: [Haskell-beginners] A try on a bank machine algorithm... To: Bernhard Lehnert <b.lehn...@gmx.de> Cc: beginners <beginners@haskell.org> Message-ID: <4a23ebe2.3040...@suud.de> Content-Type: text/plain; charset=windows-1252; format=flowed Bernhard Lehnert wrote: > Hi, > > in a Python Forum someone came up with his homework. Just beginning to > learn Haskell I thougt I give it a try. I came up with a working > function that I present here to ask you, if I am doing this right or how > I could do better. > > The job was: A cash machine has to compute the division of bank notes > for any given amount of money. > According to German wikipedia a common algorithm is to start giving one > 5$ bill, one 10$ and so on as long as possible (I call this uphill). > After that the maximum possible amount of large bank notes is given... > > Thus every customer gets some small bills and still the number of bills > is limited. My answer is a function called 'paymixture' which first > calls a function 'uphill' and afterwards a function 'downhill', each of > which realizes one part of the above mentioned algorithm. The downhill > function might also be usefull apart from the rest which is why > indentation ist different... > > Thanks a lot, > Bernhard > ------------------------------------------------------------- > paymixture :: (Ord t, Num t)=> t->[t]->[t] > -- usage: paymixture (sum to pay) (list of possible bills) > -- list of bills has to be sorted, like in > -- 'paymixture 175 [5,10,20,50,100]' > -- last element of the returned list is what could not be paid. > > paymixture n list = init(up) ++ down > where > up = uphill n list > down = downhill (last(up)) (reverse list) > > uphill :: (Ord t, Num t)=> t->[t]->[t] > uphill n [] = [n] > uphill 0 _ = [0] > uphill n (x:xs) = if n>=x then x : uphill (n-x) xs > else uphill n xs > > downhill :: (Ord t, Num t)=> t ->[t]->[t] > -- usage: downhill (sum to pay) (list of possible bills) > -- list if bills has to be reverse sorted, like e. g. > -- 'downhill 175 [200, 100, 50, 20, 10,5]' > -- last elemt of return value is the rest that could > -- not be paid. > > downhill n supply | (n<last supply) = [n] > | otherwise = max : downhill (n-max) supply > where max = head([x|x<-supply, x<=n]) > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > Ok, I don't really think I know what you are planing to do. Say I'd like to have 175 form an ATM and [200, 100, 50, 20, 10,5] is the list of bills that can be used to cash this money. Do you what to produce a list like [0,1,1,1,0,1]? Telling you that you have to take one 100 bill, one 50 bill, etc... Then I would do it the following: cashout :: (Integral a) => a -> [a] -> [a] cashout 0 _ = [] cashout _ [] = error "*** in cashout: Not cashable." cashout tocash (b:bs) = fst r : cashout (snd r) bs where r = tocash `divMod` b prop_cashout tocash bills = tocash == sum (zipWith (*) (cashout tocash bills) bills) Hence, cashout 175 [200,100,50,20,10,5] == [0,1,1,1,0,1] But maybe you want something different. Thomas ------------------------------ Message: 8 Date: Mon, 1 Jun 2009 12:19:47 -0400 From: Brent Yorgey <byor...@seas.upenn.edu> Subject: Re: [Haskell-beginners] A try on a bank machine algorithm... To: beginners@haskell.org Message-ID: <20090601161947.ga8...@seas.upenn.edu> Content-Type: text/plain; charset=utf-8 On Mon, Jun 01, 2009 at 10:55:30AM -0400, Thomas Friedrich wrote: > > Ok, I don't really think I know what you are planing to do. Say I'd like to > have 175 ⬠form an ATM and [200, 100, 50, 20, 10,5] is the list of bills > that can be used to cash this money. Do you what to produce a list like > [0,1,1,1,0,1]? Telling you that you have to take one 100⬠bill, one 50⬠> bill, etc... > > Then I would do it the following: > > cashout :: (Integral a) => a -> [a] -> [a] > cashout 0 _ = [] > cashout _ [] = error "*** in cashout: Not cashable." > cashout tocash (b:bs) = fst r : cashout (snd r) bs > where r = tocash `divMod` b > > prop_cashout tocash bills = tocash == sum (zipWith (*) (cashout tocash > bills) bills) > > > Hence, > > cashout 175 [200,100,50,20,10,5] == [0,1,1,1,0,1] > > But maybe you want something different. It sounded to me a little different: like if you withdraw 200 â¬, you don't just want a 200 ⬠bill, you want some small bills too: so you would get two 5s, two 10s, a 20, a 50, and a 100. -Brent ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 12, Issue 1 ****************************************