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. Removing the biggest element from a list - maybe slow?
(Nathan Huesken)
2. Re: Removing the biggest element from a list - maybe slow?
(Lafras Uys)
3. Re: Removing the biggest element from a list - maybe slow?
(Lafras Uys)
4. Re: Removing the biggest element from a list - maybe slow?
(matthew coolbeth)
5. Re: Removing the biggest element from a list - maybe slow?
(Nathan Huesken)
6. Re: Removing the biggest element from a list - maybe slow?
(matthew coolbeth)
7. Re: Removing the biggest element from a list - maybe slow?
(Daniel Fischer)
8. Re: Removing the biggest element from a list - maybe slow?
(Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Mon, 24 May 2010 08:42:28 -0400
From: Nathan Huesken <hask...@lonely-star.org>
Subject: [Haskell-beginners] Removing the biggest element from a list
- maybe slow?
To: Biginners Haskell Mailinglist <beginners@haskell.org>
Message-ID: <20100524084228.6ce58...@samzwo>
Content-Type: text/plain; charset=US-ASCII
Hi,
I want to remove the biggest element from a list:
withoutBiggest (x:xs) =
withoutBiggestImpl (biggest x xs) [] (x:xs)
where
biggest :: (Ord a) => a -> [a] -> a
biggest big [] = big
biggest big (x:xs) =
if x > big then
biggest x xs
else
biggest big xs
withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
withoutBiggestImpl big before (x:xs) =
if big == x then
before ++ xs
else
withoutBiggestImpl big (before ++ [x]) xs
Works, but I am a little concerned that this is
slower than needed, because the list has to be iterated twice.
Can this be done faster?
Regards,
Nathan
------------------------------
Message: 2
Date: Mon, 24 May 2010 15:27:03 +0200
From: Lafras Uys <laf...@aims.ac.za>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: Biginners Haskell Mailinglist <beginners@haskell.org>
Message-ID: <4bfa7ea7.5060...@aims.ac.za>
Content-Type: text/plain; charset=ISO-8859-1
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
> I want to remove the biggest element from a list:
>
> withoutBiggest (x:xs) =
> withoutBiggestImpl (biggest x xs) [] (x:xs)
> where
> biggest :: (Ord a) => a -> [a] -> a
> biggest big [] = big
> biggest big (x:xs) =
> if x > big then
> biggest x xs
> else
> biggest big xs
> withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
> withoutBiggestImpl big before (x:xs) =
> if big == x then
> before ++ xs
> else
> withoutBiggestImpl big (before ++ [x]) xs
>
>
> Works, but I am a little concerned that this is
> slower than needed, because the list has to be iterated twice.
>
> Can this be done faster?
import Data.List
init sort xs
or
import Data.List
delete (maximum xs) xs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAkv6fqcACgkQKUpCd+bV+ko55wCbB/AVbb9OhfGK5ObsAc4yxVFH
YigAnjudQlhBThF2IvUOjXFknAxBHUnN
=XuKY
-----END PGP SIGNATURE-----
------------------------------
Message: 3
Date: Mon, 24 May 2010 15:33:05 +0200
From: Lafras Uys <laf...@aims.ac.za>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: Biginners Haskell Mailinglist <beginners@haskell.org>
Message-ID: <4bfa8011.2050...@aims.ac.za>
Content-Type: text/plain; charset=ISO-8859-1
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
>> withoutBiggest (x:xs) =
>> withoutBiggestImpl (biggest x xs) [] (x:xs)
>> where
>> biggest :: (Ord a) => a -> [a] -> a
>> biggest big [] = big
>> biggest big (x:xs) =
>> if x > big then
>> biggest x xs
>> else
>> biggest big xs
>> withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
>> withoutBiggestImpl big before (x:xs) =
>> if big == x then
>> before ++ xs
>> else
>> withoutBiggestImpl big (before ++ [x]) xs
>
>
>> Works, but I am a little concerned that this is
>> slower than needed, because the list has to be iterated twice.
>
>> Can this be done faster?
>
> import Data.List
> init sort xs
>
> or
>
> import Data.List
> delete (maximum xs) xs
that should be,
import Data.List
init $ sort xs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAkv6gBAACgkQKUpCd+bV+kq3aACfZFmIK3ChuVky9qWqLGYc2rrt
Np4An06oMtwCIu9pEYNumrX6N0Y5hFYn
=jKVY
-----END PGP SIGNATURE-----
------------------------------
Message: 4
Date: Mon, 24 May 2010 09:38:37 -0400
From: matthew coolbeth <mac01...@engr.uconn.edu>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: <laf...@aims.ac.za>
Cc: Biginners Haskell Mailinglist <beginners@haskell.org>
Message-ID:
<aanlktikwa8pofzc0gnfkkfkdm32zqb7e3jvaljjyw...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Mon, May 24, 2010 at 09:27, Lafras Uys <laf...@aims.ac.za> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> > I want to remove the biggest element from a list:
> >
> > withoutBiggest (x:xs) =
> > withoutBiggestImpl (biggest x xs) [] (x:xs)
> > where
> > biggest :: (Ord a) => a -> [a] -> a
> > biggest big [] = big
> > biggest big (x:xs) =
> > if x > big then
> > biggest x xs
> > else
> > biggest big xs
> > withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
> > withoutBiggestImpl big before (x:xs) =
> > if big == x then
> > before ++ xs
> > else
> > withoutBiggestImpl big (before ++ [x]) xs
> >
> >
> > Works, but I am a little concerned that this is
> > slower than needed, because the list has to be iterated twice.
> >
> > Can this be done faster?
>
> import Data.List
> init sort xs
>
> This is not linear time. It also doesn't maintain the order of the list.
> or
>
> import Data.List
> delete (maximum xs) xs
>
I don't think you are going to do better than this. Just by the nature of
the problem, you need to go through the list twice: either forward
initially and then backward during the "return phase" of your function, or
twice forward with a pair of tail-recursive operations. The suggestion
above does the latter and, I believe, achieves optimal expenditures of both
time and space.
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAkv6fqcACgkQKUpCd+bV+ko55wCbB/AVbb9OhfGK5ObsAc4yxVFH
> YigAnjudQlhBThF2IvUOjXFknAxBHUnN
> =XuKY
> -----END PGP SIGNATURE-----
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
--
mac
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100524/d9bd1dd4/attachment-0001.html
------------------------------
Message: 5
Date: Mon, 24 May 2010 09:42:21 -0400
From: Nathan Huesken <hask...@lonely-star.org>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID: <20100524094221.3214c...@samzwo.tch.harvard.edu>
Content-Type: text/plain; charset=US-ASCII
On Mon, 24 May 2010 15:27:03 +0200
Lafras Uys <laf...@aims.ac.za> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> > I want to remove the biggest element from a list:
> >
> > withoutBiggest (x:xs) =
> > withoutBiggestImpl (biggest x xs) [] (x:xs)
> > where
> > biggest :: (Ord a) => a -> [a] -> a
> > biggest big [] = big
> > biggest big (x:xs) =
> > if x > big then
> > biggest x xs
> > else
> > biggest big xs
> > withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
> > withoutBiggestImpl big before (x:xs) =
> > if big == x then
> > before ++ xs
> > else
> > withoutBiggestImpl big (before ++ [x]) xs
> >
> >
> > Works, but I am a little concerned that this is
> > slower than needed, because the list has to be iterated twice.
> >
> > Can this be done faster?
>
> import Data.List
> init sort xs
>
> or
>
> import Data.List
> delete (maximum xs) xs
I see. I would think, the first solution takes still to much time
because it needs to sort the list.
Is "delete" a fast operation (O(1))? or does it internally traverse
the list?
Thanks!
Nathan
------------------------------
Message: 6
Date: Mon, 24 May 2010 09:49:35 -0400
From: matthew coolbeth <mac01...@engr.uconn.edu>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: Nathan Huesken <hask...@lonely-star.org>
Cc: beginners@haskell.org
Message-ID:
<aanlktil9gcxzmsdzsdnsvns0zqpor2rls8ozx5jl3...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
It is linear time, implemented roughly as below
delete z [] = []
delete z (x:xs) = if x=z then delete z xs else x:(delete z xs)
On Mon, May 24, 2010 at 09:42, Nathan Huesken <hask...@lonely-star.org>wrote:
> On Mon, 24 May 2010 15:27:03 +0200
> Lafras Uys <laf...@aims.ac.za> wrote:
>
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > > I want to remove the biggest element from a list:
> > >
> > > withoutBiggest (x:xs) =
> > > withoutBiggestImpl (biggest x xs) [] (x:xs)
> > > where
> > > biggest :: (Ord a) => a -> [a] -> a
> > > biggest big [] = big
> > > biggest big (x:xs) =
> > > if x > big then
> > > biggest x xs
> > > else
> > > biggest big xs
> > > withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
> > > withoutBiggestImpl big before (x:xs) =
> > > if big == x then
> > > before ++ xs
> > > else
> > > withoutBiggestImpl big (before ++ [x]) xs
> > >
> > >
> > > Works, but I am a little concerned that this is
> > > slower than needed, because the list has to be iterated twice.
> > >
> > > Can this be done faster?
> >
> > import Data.List
> > init sort xs
> >
> > or
> >
> > import Data.List
> > delete (maximum xs) xs
>
> I see. I would think, the first solution takes still to much time
> because it needs to sort the list.
>
> Is "delete" a fast operation (O(1))? or does it internally traverse
> the list?
>
> Thanks!
> Nathan
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
--
mac
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100524/5d6000ee/attachment-0001.html
------------------------------
Message: 7
Date: Mon, 24 May 2010 16:01:09 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID: <201005241601.10015.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="iso-8859-1"
On Monday 24 May 2010 14:42:28, Nathan Huesken wrote:
> Hi,
>
> I want to remove the biggest element from a list:
>
> withoutBiggest (x:xs) =
> withoutBiggestImpl (biggest x xs) [] (x:xs)
> where
> biggest :: (Ord a) => a -> [a] -> a
> biggest big [] = big
> biggest big (x:xs) =
> if x > big then
> biggest x xs
> else
> biggest big xs
> withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
> withoutBiggestImpl big before (x:xs) =
> if big == x then
> before ++ xs
> else
> withoutBiggestImpl big (before ++ [x]) xs
>
Just to make sure, you are aware that this removes only the first
occurrence of the largest element if there are several?
In that code, collecting the before-list is
a) unnecessary
b) inefficient
Re b), consider the list [1 .. n] for some large n.
Then you have
wBI n [] [1 .. n]
~> wBI n ([]++[1]) [2 .. n]
~> wBI n (([] ++ [1]) ++ [2]) [3 .. n]
~> wBI n ((([] ++ [1]) ++ [2]) ++ [3]) [4 .. n]
~> ...
~> wBI n ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1]) [n]
~> ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1])
And:
Prelude> let func :: Int -> Int; func n = last (foldl (\xs k -> xs ++ [k])
[] [1 .. n])
(0.00 secs, 524224 bytes)
Prelude> func 5000
5000
(0.44 secs, 351528996 bytes)
Prelude> func 10000
10000
(2.63 secs, 1404077120 bytes)
Prelude> func 20000
20000
(20.03 secs, 5613242020 bytes)
Ouch.
The short code to achieve the same is (as has been posted before)
import Data.List
withoutBiggest [] = []
withoutBiggets xs = delete (maximum xs) xs
That also traverses the list twice, but is much faster because it doesn't
build a left-nested chain of (++)-applications.
Like your code, it requires the entire list to be in memory though.
If you need the elements in the original order (except the first occurrence
of the maximum), you can't completely eliminate that memory requirement,
though you can reduce it somewhat on average (ugly code, not more efficient
than delete (maxumum xs) xs in general, worst case considerably slower).
If you don't need to retain the order, you can efficiently do it with one
traversal.
withoutLargest [] = []
withoutLargest (x:xs) = go x xs
where
go _ [] = []
go p (y:ys)
| p < y = p : go y ys
| otherwise = y : go p ys
>
> Works, but I am a little concerned that this is
> slower than needed, because the list has to be iterated twice.
>
> Can this be done faster?
>
> Regards,
> Nathan
------------------------------
Message: 8
Date: Mon, 24 May 2010 16:04:37 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID: <201005241604.37369.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="utf-8"
On Monday 24 May 2010 15:49:35, matthew coolbeth wrote:
> It is linear time, implemented roughly as below
>
> delete z [] = []
> delete z (x:xs) = if x=z then delete z xs else x:(delete z xs)
>
delete only deletes the first occurrence, so it's equivalent to
delete z (x:xs)
| x == z = xs
| otherwise = x : delete z xs
delete _ [] = []
, it's O(index of z) thus.
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 36
*****************************************
