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: appropriateness of haskell for GUIs (Thomas Davie)
2. Re: appropriateness of haskell for GUIs (Michael Mossey)
3. laziness and optimization (Michael Mossey)
4. about beta NF in lambda calculus (Algebras Math)
5. Re: laziness and optimization (Brent Yorgey)
6. Re: about beta NF in lambda calculus (Brent Yorgey)
7. Re: about beta NF in lambda calculus (Brent Yorgey)
8. splitWith and foldr stack overflow (Sean Bartell)
----------------------------------------------------------------------
Message: 1
Date: Sat, 21 Mar 2009 11:06:36 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] appropriateness of haskell for GUIs
To: Michael P Mossey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 21 Mar 2009, at 00:16, Michael P Mossey wrote:
> Hello, I'm totally new to Haskell. I'm thinking of using it for a
> personal project, which is a gui-based musical score editor. (*) Why
> Haskell? I've always been interested in proving my software's
> correctness, usually in practical and informal sense. In other
> words, I would like to reduce bugs by having a really good
> understanding of what my software does. I also just want to learn
> Haskell.
>
> Before I invest a lot of time in learning Haskell, however, I want
> to understand if it's the right language for doing a gui-based
> musical score editor. First of all, I need a gui toolkit of some
> sort, and I notice that bindings to Qt exist. I'm already very
> familiar with Qt, so that's good. I also need to access the Windows
> midi api, and I see there is a module called hmidi.
>
> However, a gui program is essentially event driven and heavily
> interacts with the outside world. I don't know how compatible these
> ideas are with Haskell.
>
> If I don't use Haskell, I will probably use Python, which I already
> know well. So basically the question is: Haskell or Python? Note: I
> would enjoy learning Haskell, so this is not a question of which
> language is better in an absolute sense... if Haskell is suitable,
> but not the best choice, I will still probably use it.
The rough situation of GUI programming on Haskell is that it works
just as well as in any imperative programming language. This is
rather disappointing, simply because so many other things are
massively easier in Haskell, and this isn't true of GUI programming
(yet).
There are various efforts to write more functional GUI environments
(Grapefruit, reactive, yampa, etc), but none are yet {stable | mature
| scalable | some other reason} enough to use in production.
Bob
------------------------------
Message: 2
Date: Sat, 21 Mar 2009 05:30:17 -0700
From: Michael Mossey <[email protected]>
Subject: Re: [Haskell-beginners] appropriateness of haskell for GUIs
To: Thomas Davie <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Thomas Davie wrote:
>
> On 21 Mar 2009, at 00:16, Michael P Mossey wrote:
>
>> Hello, I'm totally new to Haskell. I'm thinking of using it for a
>> personal project, which is a gui-based musical score editor.
>
> The rough situation of GUI programming on Haskell is that it works just
> as well as in any imperative programming language. This is rather
> disappointing, simply because so many other things are massively easier
> in Haskell, and this isn't true of GUI programming (yet).
Hi Bob,
I can imagine that GUI programming is no easier (yet). It is inherently
very "stateful." GUI's have modes, such as which screens are displayed,
which dialogs are displayed, which options within those dialogs are
valid given the other state of the program, etc. When I write GUIs, I
often diagram them as state machines to get a handle on what's going on.
So, I'm not familiar with GUI programming on Haskell, but would you say
the statefulness of GUIs (in their typical implementations) is the
reason they are no easier on Haskell?
I strongly prefer to use qtHaskell because I'm familiar with Qt, and Qt
is extremely capable. For example, it can draw text and shapes with
antialiasing, which will be great for a music score editor. Music scores
have lots of small shapes to fit on the screen, and antialiasing will
provide ease of reading. I don't know how much of Qt is implemented in
qtHaskell, or whether the latest version of Qt (4.4) is implemented.
Thanks,
Mike
------------------------------
Message: 3
Date: Sat, 21 Mar 2009 06:02:58 -0700
From: Michael Mossey <[email protected]>
Subject: [Haskell-beginners] laziness and optimization
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
I understand a bit about the concept of "lazy evaluation." I think of
that as saying an imperative language would always make one evaluation,
whereas Haskell might make 0 evaluations. I have another similar
situation where an imperative language would make N evaluations of the
same expression, and I would like Haskell to make only 1.
This is the situation: the graphical score editor displays
"LayoutItems." A LayoutItem can be a single displayed entity, like a
round notehead, or it can be composed of several entities.
A common situation in my code is the need to determine the size and
shape of a LayoutItem. For a fundamental item, this can be looked up in
a table or read from the font properties. For a composite item, some
computation is required: the code must determine the positions of each
sub-item and compute the bounds of a shape containing all of them.
It's this latter computation, finding the bounds of a composite item,
which might come up multiple times. Consider that I ask for the bounds
of a composite-composite item (a composite item composed of composite
items). It will run the computation associated with each composite
sub-item, even though it is very likely I already make that computation
when I first constructed and placed that sub-item.
In an imperative language, one might cache values for later lookup. This
raises the problem of keeping the cache current to the current state.
So I'm wondering to what extent the haskell compiler recognizes
computations it's done before. In a purely functional language this
should be pretty easy, right? If it sees the same expression, it knows
it will have the same value. That's my understanding, so far.
Thanks,
Mike
------------------------------
Message: 4
Date: Sat, 21 Mar 2009 19:28:48 +0000
From: Algebras Math <[email protected]>
Subject: [Haskell-beginners] about beta NF in lambda calculus
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
hi,
What is the different between 'in beta normal form' and 'has beta normal
form' ? Does the former means the current form of the term is already in
normal form but the latter means that it is not a normal form yet and can be
reduced to be normal form? Like \x.x is in NF and (\x.x) (\x.x) has NF?
If above is true, I am confused why we have to distinguish the terms which
have NF and be in NF? isn't the terms have NF will eventually become in NF?
or there are some way to avoid them becoming in NF?
Thanks
Alg
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090321/1767864e/attachment-0001.htm
------------------------------
Message: 5
Date: Sat, 21 Mar 2009 15:30:03 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] laziness and optimization
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 21, 2009 at 06:02:58AM -0700, Michael Mossey wrote:
>
> So I'm wondering to what extent the haskell compiler recognizes
> computations it's done before. In a purely functional language this should
> be pretty easy, right? If it sees the same expression, it knows it will
> have the same value. That's my understanding, so far.
It really doesn't; this isn't as easy in a purely functional language
as you think. For one thing, how to recognize which computations have
been done before? The runtime would have to keep around some sort of
hash mapping expressions to values, and incur a lot of overhead
checking each thing to be evaluated against this map. Furthermore,
this may be very expensive memory-wise. Consider the the case where
some expression generates a very long (say, million-element) list, but
it is immediately processed by some other code which counts how many
threes the list contains. This can be done in constant memory, since
the garbage collector can come along behind and clean up the processed
parts of the list even while it is still being generated. But if we
need to keep the list around just in case the expression that
generated it is used again, we will need to keep a million-element
list in memory! So sometimes, memoizing expression values like this
is a pessimization, and it's very difficult to tell the difference.
This is a tricky problem; I've run into pretty much the exact same
problem (the need to cache computed sizes for recursively constructed
elements) in my 'diagrams' library. Probably the easiest solution
(which I haven't actually yet implemented in my library, but plan to
do something along these lines!) is just to cache the size like you
would in an imperative language. For example:
data Thingy = Composite [Sized Thingy]
| Primitive String
data Sized a = S { size :: Int, thing :: a }
thingySize :: Thingy -> Int
thingySize (Primitive s) = length s
thingySize (Composite sts) = sum (map size sts)
mkSizedThingy :: Thingy -> Sized Thingy
mkSizedThingy t = S (thingySize t) t
This has exactly the property you want: due to laziness, the size of a
SizedThingy will be computed *only* if it is ever needed; and it will
be computed at most once.
-Brent
------------------------------
Message: 6
Date: Sat, 21 Mar 2009 15:37:15 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] about beta NF in lambda calculus
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 21, 2009 at 07:28:48PM +0000, Algebras Math wrote:
> hi,
>
> What is the different between 'in beta normal form' and 'has beta normal
> form' ? Does the former means the current form of the term is already in
> normal form but the latter means that it is not a normal form yet and can be
> reduced to be normal form? Like \x.x is in NF and (\x.x) (\x.x) has NF?
Exactly.
> If above is true, I am confused why we have to distinguish the terms which
> have NF and be in NF? isn't the terms have NF will eventually become in NF?
> or there are some way to avoid them becoming in NF?
If a term _has_ a normal form, we can be confident that we will
eventually reach a normal form by reducing it; if a term _is in_
normal form, we know that reducing it will have no effect. It is
useful to distinguish them in the same way as it is useful to
distinguish between someone who _is currently_ at home and someone who
is at the grocery store but has a way of getting home. (\x.x) (\x.x)
reduces to \x.x, but they are not the same term. We could "avoid"
having (\x.x) (\x.x) become a normal form by simply choosing not to
reduce it.
Does that help?
-Brent
------------------------------
Message: 7
Date: Sat, 21 Mar 2009 16:18:50 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] about beta NF in lambda calculus
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 21, 2009 at 07:59:25PM +0000, Algebras Math wrote:
> sorry, I missed something..
>
> actually (\x.x) (\x.x) reduces to \x.x, they are equal under beta
> reduction, isn't it?
> (\x.x) (\x.x) =beta \x.x.
>
> so they are the same?
It depends what you mean by "equal", but usually what we mean by
"equal" is actual structural equality, so (\x.x) (\x.x) and \x.x are
not equal, since they are different terms (one is an application of
one term to another, the other is a lambda term). It makes no
difference whether one reduces to the other; they are not the _same_
term so they are not equal.*
However, sometimes we _don't_ want to distinguish between terms which
reduce to one another; in this case we can define some sort of
equivalence relation, and say, for example, S =beta T if S can be
reduced to T by a series of beta reductions, or vice versa. But it is
important to realize that =beta is just an equivalence relation we
have defined, it is not the same thing as equality. It is quite
possible to have S =beta T but S /= T, as in your example.
-Brent
*Technical note: actually, we usually allow terms to be equal "up to
alpha equivalence", that is, you are allowed to rename bound
variables. So (\x.x) and (\y.y) are equal, since you can convert
between them by renaming x to y, which doesn't really change anything.
>
> On Sat, Mar 21, 2009 at 7:37 PM, Brent Yorgey <[email protected]>wrote:
>
> > On Sat, Mar 21, 2009 at 07:28:48PM +0000, Algebras Math wrote:
> > > hi,
> > >
> > > What is the different between 'in beta normal form' and 'has beta normal
> > > form' ? Does the former means the current form of the term is already in
> > > normal form but the latter means that it is not a normal form yet and can
> > be
> > > reduced to be normal form? Like \x.x is in NF and (\x.x) (\x.x) has NF?
> >
> > Exactly.
> >
> > > If above is true, I am confused why we have to distinguish the terms
> > which
> > > have NF and be in NF? isn't the terms have NF will eventually become in
> > NF?
> > > or there are some way to avoid them becoming in NF?
> >
> > If a term _has_ a normal form, we can be confident that we will
> > eventually reach a normal form by reducing it; if a term _is in_
> > normal form, we know that reducing it will have no effect. It is
> > useful to distinguish them in the same way as it is useful to
> > distinguish between someone who _is currently_ at home and someone who
> > is at the grocery store but has a way of getting home. (\x.x) (\x.x)
> > reduces to \x.x, but they are not the same term. We could "avoid"
> > having (\x.x) (\x.x) become a normal form by simply choosing not to
> > reduce it.
> >
> > Does that help?
> >
> > -Brent
> > _______________________________________________
> > Beginners mailing list
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
> >
------------------------------
Message: 8
Date: Sun, 22 Mar 2009 12:26:35 -0400
From: Sean Bartell <[email protected]>
Subject: [Haskell-beginners] splitWith and foldr stack overflow
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
I wrote a splitWith function (from RWH) and then converted it to use foldr:
splitWith, splitWith2 :: (a -> Bool) -> [a] -> [[a]]
splitWith p xs = let (ls, ts) = f xs in ts:ls
where f [] = ([], [])
f (x:xs) | p x = (ls, x:ts)
| otherwise = (ts:ls, [])
where (ls, ts) = f xs
splitWith2 p xs = let (ls, ts) = foldr f ([],[]) xs in ts:ls
where f x (ls, ts) | p x = (ls, x:ts)
| otherwise = (ts:ls, [])
Tested with something simple like
take 8 $ splitWith id (cycle [False,True])
splitWith works fine, but splitWith2 causes a stack overflow. Don't
they have the same recursive structure, though?
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 26
****************************************
