mrvr84:
>
>What's the best way to implement the following function in
>haskell: Given a list and an integer k as input return the
>indices of the least k elements in the list. The code should
>be elegant and also, more importantly, must not make more
>than the minimum O(k*lengt
On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
> What's the best way to implement the following function in haskell:
> Given a list and an integer k as input return the indices of the least
> k elements in the list. The code should be elegant and also, more
> importantly, must not m
On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
> On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
> > What's the best way to implement the following function in haskell:
> > Given a list and an integer k as input return the indices of the least
> > k elements in the li
On 4/11/07, Stefan O'Rear <[EMAIL PROTECTED]> wrote:
If you want to be really explicit about it, here is a sort that will
work:
sort [] = []
sort l@(x:_) = filter (x) l
(A stable quicksort, btw)
You may be missing a few recursive calls there :-)
Cheers,
Tim
--
Tim Chevalier * [EMAIL PROTEC
On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:
> On 4/11/07, Stefan O'Rear <[EMAIL PROTECTED]> wrote:
> >
> >If you want to be really explicit about it, here is a sort that will
> >work:
> >
> >sort [] = []
> >sort l@(x:_) = filter (x) l
> >
> >(A stable quicksort, btw)
>
> You may
IL PROTECTED]>
Sent: Wednesday, 11 April, 2007 11:17:15 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Thu, Apr 12, 2007 at 09:30:22AM +0530, raghu vardhan wrote:
> Hmmm. That's not something I was looking for. I'm not sure the
> running time is good enough (think of k
G'day all.
Quoting raghu vardhan <[EMAIL PROTECTED]>:
> What's the best way to implement the following function in haskell:
> Given a list and an integer k as input return the indices of the least k
> elements in the list. The code should be elegant and also, more importantly,
> must not make mor
to do this).
- Original Message
From: Stefan O'Rear <[EMAIL PROTECTED]>
To: raghu vardhan <[EMAIL PROTECTED]>
Cc: [EMAIL PROTECTED]
Sent: Wednesday, 11 April, 2007 10:47:08 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Wed, Apr 11, 2007 at 08:38:48PM -0700, Ste
G'day all.
Quoting raghu vardhan <[EMAIL PROTECTED]>:
> So, any algorithm that sorts is no good (think of n as huge, and k small).
The essence of all the answers that you've received is that it doesn't
matter if k is small, sorting is still the most elegant answer in Haskell.
The reason is that
[sorry for the double, ajb]
Since there seemed to be a disconnect between the expectation and
the previous answers, I thought an alternative suggestion might help
out. This sort of thing (haha) usually isn't my cup o' tea, so please
point out any blunders.
RM, is this more like what you had in m
On Thu, 12 Apr 2007, raghu vardhan wrote:
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least k
elements in the list. The code should be elegant and also, more importantly,
must not make more than the minimu
On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
To get the indices, use the Schwartzian transform:
sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
sortWith f = mergeRuns . runs
where
runs = map (:[])
mergeRuns [] = []
mergeRuns [xs] = xs
mergeRuns xss = mergeRuns (merge
Kurt Hutchinson wrote:
> On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>> To get the indices, use the Schwartzian transform:
>>
>> sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
>> sortWith f = mergeRuns . runs
>> where
>> runs = map (:[])
>>
>> mergeRuns [] = []
>> mergeRun
The link pretty much answers my question, though you probably require a
little bit more book keeping to get the indices out. Compared to the
iterative version or the matlab version, this definitely is more elegant,
but also is trickier.
apfelmus wrote:
>
> raghu vardhan <[EMAIL PROTECTED]>:
>
\begin{code}
kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
where
(h, t) = splitAt k $ zip x [0..]
insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
| e < mx= Set.insert e s'
| otherwise = s
where
(mx
\begin{code}
kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
where
(h, t) = splitAt k $ zip x [0..]
insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
| e < mx= Set.insert e s'
| otherwise = s
where
(mx
G'day all.
Quoting Kurt Hutchinson <[EMAIL PROTECTED]>:
> For my own edification, what is the benefit of this sortWith over sortBy?
None. I wanted to write my own sort, illustrating how the lazy
evaluation thing works, and I didn't want a name clash with an
existing library function.
Cheers,
A
> You may be missing a few recursive calls there :-)
Indeed.
I'm confused.
Is this a legitimate stable quicksort, or not? (My guess is, it is
indeed legit as written.)
This was also the first I have heard of stability as a sort property.
http://perldoc.perl.org/sort.html may shed some light
And for reference, here is again stefan's "stable" quicksort from his
earlier post.
"
sort [] = []
sort l@(x:_) = filter (x) l
(A stable quicksort, btw)
"
This is the code whose legitimacy I am requesting confirmation of.
2007/4/13, Thomas Hartman <[EMAIL PROTECTED]>:
> > You may be missing a
Trying to understand this better I also came across
http://groups.google.de/group/fa.haskell/browse_thread/thread/1345c49faff85926/8f675bd2aeaa02ba?lnk=st&q=%22I+assume+that+you+want+to+find+the+k%27th+smallest+element%22&rnum=1&hl=en#8f675bd2aeaa02ba
where apfulmus gives an implementation of me
Rereading this, I see in fact apfelmus explains this is
"O(n + k*log n)" for the first k elements, which this discussion also
maintains is the best case. So, there's no discrepancy.
I think this is a very valuable post to read for the explanation.
2007/4/13, Thomas Hartman <[EMAIL PROTECTED]>:
G'day all.
Quoting Thomas Hartman <[EMAIL PROTECTED]>:
> Does that mean you can have the k minima in O(n) time, where n is
> length of list, which would seem to be an improvement?
It's worth considering what the theoretical minimum is.
You have n elements, and you need to locate a specific k-el
Hello,
My Hugs tells me this:
Prelude> let sort [] = []; sort l@(x:_) = filter (x) l in sort [1,3,2]
[1,3,2]
Prelude>
So, no, this is not a working sorting function. Inserting the "few missing
recursive calls":
Prelude> let sort [] = []; sort l@(x:_) = sort ( filter (x) l ) in sort [1,3,2]
[1,
On Fri, Apr 13, 2007 at 07:32:20AM -0400, [EMAIL PROTECTED] wrote:
>
> Quoting Thomas Hartman <[EMAIL PROTECTED]>:
>
> > Does that mean you can have the k minima in O(n) time, where n is
> > length of list, which would seem to be an improvement?
>
> It's worth considering what the theoretical mi
On 4/13/07, Ian Lynagh <[EMAIL PROTECTED]> wrote:
Tuple each element with its position: O(n)
Find kth smallest element in linear time, as per [1]: O(n)
Filter list for elements <= kth smallest: O(n)
Sort filtered list by position: O(k log k)
map
G'day all.
I wrote:
> > O(log(n! / (n-k)!))
> > = O(n log n - (n-k) log (n-k))
> > = O(n log (n/(n-k)) + k log (n-k))
> >
> > That looks right to me. If k << n, then this simplifies to
> > O(n + k log n), and if k is close to n, it simplifies to
> > O(n log n + k).
Quoting Ian Lynagh <[EMAIL
Yitz writes (in the Haskell Cafe):
This gives O(log k * (n + k)) execution in constant memory.
I guess that should be O(k) memory.
Cheers,
Ronny Wichers Schreur
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/
27 matches
Mail list logo