Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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 <[email protected]>
Subject: Re: [Haskell-beginners] Maybe a and Maybe t
Cc: [email protected]
Message-ID: <[email protected]>
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
[email protected]
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 <[email protected]>
Subject: Re: [Haskell-beginners] Maybe a and Maybe t
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: [Haskell-beginners] A try on a bank machine algorithm...
To: beginners <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Maybe a and Maybe t
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] A try on a bank machine algorithm...
To: Bernhard Lehnert <[email protected]>
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, May 31, 2009 at 2:19 PM, Bernhard Lehnert <[email protected]> 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
> [email protected]
> 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 <[email protected]>
Subject: Re: [Haskell-beginners] Maybe a and Maybe t
To: [email protected]
Message-ID: <[email protected]>
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
[email protected]
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 <[email protected]>
Subject: Re: [Haskell-beginners] A try on a bank machine algorithm...
To: Bernhard Lehnert <[email protected]>
Cc: beginners <[email protected]>
Message-ID: <[email protected]>
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
> [email protected]
> 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 <[email protected]>
Subject: Re: [Haskell-beginners] A try on a bank machine algorithm...
To: [email protected]
Message-ID: <[email protected]>
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
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 12, Issue 1
****************************************
