headers
Andrew J Bromage | 1 Jan 2003 03:26
Favicon
Gravatar

Re: Question About lists

G'day all.

On Mon, Dec 30, 2002 at 01:47:37PM -0600, Artie Gold wrote:

> One suggestion, though is that you're working too hard; there's really 
> no reason to define a locally defined function. The much simpler:
> 
> long [] = 0
> long (x:xs) = 1 + long xs
> 
> will do quite nicely.

It has quite different performance characteristics, though.  In
particular, this uses O(n) stack space whereas the accumulator one
uses O(1) stack space.

Cheers,
Andrew Bromage
Permalink | Reply | 4 comments |
headers
Shlomi Fish | 1 Jan 2003 11:17
Picon

Re: Question About lists

On Wed, 1 Jan 2003, Andrew J Bromage wrote:

> G'day all.
>
> On Mon, Dec 30, 2002 at 01:47:37PM -0600, Artie Gold wrote:
>
> > One suggestion, though is that you're working too hard; there's really
> > no reason to define a locally defined function. The much simpler:
> >
> > long [] = 0
> > long (x:xs) = 1 + long xs
> >
> > will do quite nicely.
>
> It has quite different performance characteristics, though.  In
> particular, this uses O(n) stack space whereas the accumulator one
> uses O(1) stack space.
>

This is assuming Haskell is properly tail-recursive. However, as far as I
was told due to the lazy evaluation that is not the case for such
functions.

Regards,

	Shlomi Fish

> Cheers,
> Andrew Bromage
> _______________________________________________
(Continue reading)

Permalink | Reply | 3 comments |
headers
Andrew J Bromage | 2 Jan 2003 01:57
Favicon
Gravatar

Re: Question About lists

G'day all.

On Wed, 1 Jan 2003, Andrew J Bromage wrote:

> > It has quite different performance characteristics, though.  In
> > particular, this uses O(n) stack space whereas the accumulator one
> > uses O(1) stack space.

On Wed, Jan 01, 2003 at 12:17:10PM +0200, Shlomi Fish wrote:

> This is assuming Haskell is properly tail-recursive. However, as far as I
> was told due to the lazy evaluation that is not the case for such
> functions.

There are two issues here:

1. Haskell 98 does not explicitly mandate tail recursion optimisation.
(In particular, Hugs doesn't support it fully, as we have seen
recently.)

2. Due to lazy evaluation, your accumulator may end up as a "thunk" and
thus require stack/heap space to evaluate when you eventually get to
the end.

There's not a lot you can do about the first issue.  The next version
of Haskell should make tail recursion optimisation a language
requirement, IMO.

As to the second point, there are several possible solutions.
(Continue reading)

Permalink | Reply | 2 comments |
headers
Alastair Reid | 2 Jan 2003 09:39
Picon

Re: Question About lists


> 1. Haskell 98 does not explicitly mandate tail recursion optimisation.

However, in practice Haskell compilers must provide this since it is
impossible to write a loop without using recursion and if your loops
don't use constant stack space, you're not going to run for very long.

> (In particular, Hugs doesn't support it fully, as we have seen recently.)

Please note that this is NOT TRUE!

Hugs provides tail recursion just as fully as GHC.

What Hugs does not do is garbage collect unreachable CAFs.  This affects
top level definitions of the form:

   foo = <whatever>

which is the form of all the examples recently discussed.

--
Alastair Reid                 alastair <at> reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/
Permalink | Reply | 1 comment |
headers
Andrew J Bromage | 3 Jan 2003 00:13
Favicon
Gravatar

Re: Question About lists

G'day all.

On Thu, Jan 02, 2003 at 08:39:18AM +0000, Alastair Reid wrote:

> Please note that this is NOT TRUE!

Whoops, you're right.  Sorry, my mistake.

Cheers,
Andrew Bromage
Permalink | Reply | 0 comments |
headers
Tim Barbour | 2 Jan 2003 18:26
Picon

long delayed messages [was Re: tuple component functions]

Vinicius Callegari writes:
 [...]
 > Tim, watch out, your date is in the past. You messages might not be read...

Thanks for the warning. The messages were indeed sent in the past, and took an
unusually long time to be delivered!

Apparently a few messages got queued somewhere by my MTA (perhaps because of a
temporary configuration error), and were not sent until today... Coincidentally
I am upgrading my Debian installation - presumably this caused the queued mail
to get flushed.

Sorry about any confusion caused.

Tim
Permalink | Reply | 0 comments |
headers
Matthew Donadio | 3 Jan 2003 05:50
Picon

Questions from New-Old User

Hi all,

I hope everyone had a nice holiday season.

I am picking up a project that I started a few years ago, but for
various reasons stopped working on.  It was the Libraries for Digital
Signal Processing listed in the Numerical Algorithms and Mathematics
section on the haskell.org website.  I am going to revisit those
libraries and expand the scope a little bit to include spectral
estimation and some matrix math routines.

Anyway, since I haven't done any Haskell in about three years, I am a
bit rusty. :)  I have one question right now, and would like some advice
on another matter.  I am sure I will have other questions until the
proper section of my brain wakes up.

First, I cannot get a function to type.  The basic definition is:

rxx x k | k >= 0 = sum [ (conjugate (x!k)) * x!(n+k) | k <- [0..(n-1-k)]
] / n
	| k < 0  = conjugate (rxx x (-k))
	where n = snd (bounds x) + 1

This function performs autocorrelation for a complex array, and returns
a complex value.  The array indexes are integral in the general sense,
but could be safely Int.  I have tried various combinations of explicit
types and numeric type coersion functions without any success.  Any help
would be appreciated.

The second question has to do with the numeric class system.  In signal
(Continue reading)

Permalink | Reply | 1 comment |
headers
Glynn Clements | 3 Jan 2003 07:04
Favicon

Re: Questions from New-Old User


Matthew Donadio wrote:

> First, I cannot get a function to type.  The basic definition is:
> 
> rxx x k | k >= 0 = sum [ (conjugate (x!k)) * x!(n+k) | k <- [0..(n-1-k)]
> ] / n
> 	| k < 0  = conjugate (rxx x (-k))
> 	where n = snd (bounds x) + 1
> 
> This function performs autocorrelation for a complex array, and returns
> a complex value.  The array indexes are integral in the general sense,
> but could be safely Int.  I have tried various combinations of explicit
> types and numeric type coersion functions without any success.  Any help
> would be appreciated.

My guess is that you didn't intend n to be complex, but it's being
inferred as such (the numerator of the division is determined to be
complex from the return type of conjugate, hence the denominator must
also be complex).

If this is the case, then you probably want something like:

        rxx x k | k >= 0 = sum [ ... ] / fromIntegral n
                                         ^^^^^^^^^^^^

This works for both ghc (5.04.2) and hugs (Dec 2001).

> The second question has to do with the numeric class system.  In signal
> processing and spectral estimation, there are a lot of algorithms that
(Continue reading)

Permalink | Reply | 0 comments |
headers
Keith Wansbrough | 3 Jan 2003 12:21
Picon
Picon
Favicon

New Wiki (was: Re: ANNOUNCE: Haskell Wiki resurrected )

There have been several suggestions that we switch from the present 
pywiki, which has proven rather unstable, to something a little more 
modern and reliable.  IIRC, the suggestions have been

  MoinMoin  http://moin.sourceforge.net/
  UseMod    http://www.usemod.com/cgi-bin/wiki.pl?UseModWiki

although I'm sure there are many possibilities.

It looks to me like UseMod would be a reasonable choice, so unless there are any objections I plan to attempt
migration in the near future (modulo work demands, of course).

Any comments?

John Meacham wrote:

> What do people feel about switching to a better Wiki implementation? I
> know we all have been secretly hoping a Wiki implemented in haskell
> would surface, but this is certainly an area which is already
> overcrowded and I think the community would be better served by a fully
> functional Wiki now. I highly recommend UseMod, 
> http://www.usemod.com/cgi-bin/wiki.pl?UseModWiki
> It is very easy to set up and provides useful features like online
> browsing of Diffs and being much more robust than pywiki.

--KW 8-)
--

-- 
Keith Wansbrough <kw217 <at> cl.cam.ac.uk>
http://www.cl.cam.ac.uk/users/kw217/
University of Cambridge Computer Laboratory.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Ketil Z. Malde | 3 Jan 2003 12:50
Picon
Picon

Re: tuple component functions

<trb <at> eastpac.com.au> writes:

> S.D.Mechveliani writes:

>> As Haskell has the standard functions  fst, snd  to decompose  (a,b),
>> maybe, it worths to provide also [...]

> I've found some of these useful, except I named them differently:

>> fst3 :: (a,b,c) -> a
>> snd3 :: (a,b,c) -> b
>> thd3 :: (a,b,c) -> c

> .... never got around to quadruples etc.

I'd like a general 'nth', but of course that would restrict us to
monotyped tuples (e.g.,

        nth :: Int -> (a,a,...,a,a) -> a
) 

This isn't possible to do more generally with some language extension,
is it?

A better way might be to define classes:

class TwoTuple t a b | t -> a b where
        fst :: t -> a
        snd :: t -> b
(Continue reading)

Permalink | Reply | 0 comments |

Gmane