how to split at half a list?
ZeD
half :: [a] -> ([a],[a])
half list =
splitAt (fromEnum ((toEnum (length list))/2)) list
but I really dislike the
Int -> toEnum -> /2 -> fromEnum
Is there a better (more beauty?) way to accomplish this task?
--
Under construction
Kalman Noel
Not sure, but isn't integer division all you need?
Prelude> let half list = splitAt (length list `div` 2) list
Prelude> half [1,2,3,4,5,6]
([1,2,3],[4,5,6])
Prelude> half [1,2,3,4,5,6,7]
([1,2,3],[4,5,6,7])
Kalman
ZeD
>> but I really dislike the
>> Int -> toEnum -> /2 -> fromEnum
>>
>> Is there a better (more beauty?) way to accomplish this task?
> Not sure, but isn't integer division all you need?
yes, I really forgot about div... sorry for this stupid question
--
Under construction
Mark T.B. Carroll
> yes, I really forgot about div... sorry for this stupid question
No problem, we're here to help, and it can be hard to find your way
around what Haskell offers while you're still learning. I still try
to make time to re-read the Prelude occasionally.
-- Mark
Lutz Donnerhacke
> half :: [a] -> ([a],[a])
> half list =
> splitAt (fromEnum ((toEnum (length list))/2)) list
>
> but I really dislike the
> Int -> toEnum -> /2 -> fromEnum
>
> Is there a better (more beauty?) way to accomplish this task?
Try to use the list as an implicit counter:
half xs = splitAtEmpty (everySecond xs) xs
everySecond (x:_:xs) = x:everySecond xs
everySecond _ = []
splitAtEmpty (_:cs) (x:xs) = let (xs',ys') = splitAtEmpty cs xs
in (x:xs',ys')
splitAtEmpty _ xs = ([] ,xs )
Matthias Blume
You might want to consult Danvy's "There and back again" paper.
(Google it!)
Johannes Waldmann
> * ZeD wrote:
>> half :: [a] -> ([a],[a])
>> half list =
>> splitAt (fromEnum ((toEnum (length list))/2)) list
I wonder why you might want to do that. Could be "merge sort",
but there you'd actually need "split an (unordered) collection
into two parts of roughly equal size" and that might be achievable
by some other collection implementation in much less time
(i. e. without complete traversal). But then, if you think of having
a different collection implementation (than lists),
perhaps this already takes into account (during construction)
the ordering of the elements so you don't need the mergesort in the
first place (because you rather do toAscList . fromList)
So, what I'm saying is something like,
while programming exercise are fine to keep students busy,
the "real" programmer should avoid programming and use a library :-)
Dirk Thierbach
> ZeD <vito.d...@gmail.com> writes:
>> I have this function
half :: [a] -> ([a],[a])
half list = splitAt (length list `div` 2) list
>> Is there a better (more beauty?) way to accomplish this task?
> You might want to consult Danvy's "There and back again" paper.
Nice paper (which I hadn't seen before), but I am not sure it applies
here. "length" doesn't need to build an intermediate list, and "splitAt"
in the more efficient non-prelude version present e.g. in GHC already
uses this pattern.
And Lutz's proposal just replaces the traversal of the list by
"length" with a traversal in the second argument of the main
function. I am not sure if this is more efficient.
So I guess the above version is probably the one to choose, while at the
same time being the most obvious, and the most easily readable.
- Dirk
Mark T.B. Carroll
>> * ZeD wrote:
>>> half :: [a] -> ([a],[a])
>>> half list =
>>> splitAt (fromEnum ((toEnum (length list))/2)) list
>
> I wonder why you might want to do that. Could be "merge sort",
> but there you'd actually need "split an (unordered) collection
> into two parts of roughly equal size" and that might be achievable
> by some other collection implementation in much less time
> (i. e. without complete traversal).
(snip)
Normally for merge sort I split everything into singletons with
something like map return :: [a] -> [[a]] and then I'm ready to start
merging the list pairs. I might have been tempted to use something like
the above `half' in a recursive function for constructing a binary
search tree from a sorted list, though, given that it basically returns
(left, element : right) in a nicely-balanced way, but I'm guessing
that's an O(n^2) algorithm and I think you can make such a tree in O(n).
-- Mark
Matthias Blume
I agree that Danvy's approach is not necessarily more efficient. In
many cases it will be less efficient. I also find it a bit obscure.
But beauty is in the eye of the beholder, and I thought the OP might
appreciate Danvy's ideas since he indicated he was looking for
"beauty", not "effficiency".
Cheers,
Matthias
Andrew J. Bromage
On Apr 5, 6:32 pm, Johannes Waldmann <waldm...@imn.htwk-leipzig.de>
wrote:
> I wonder why you might want to do that. Could be "merge sort",
> but there you'd actually need "split an (unordered) collection
> into two parts of roughly equal size" and that might be achievable
> by some other collection implementation in much less time
> (i. e. without complete traversal).
I was wondering that myself. Though not about the other collection.
If you just want half-size lists and order doesn't matter,
then don't count at all:
half :: [a] -> ([a],[a])
half xs = half' xs [] []
where
half' [] xs1 xs2 = (xs1,xs2)
half' [x] xs1 xs2 = (x:xs1,xs2)
half' (x1:x2:xs) xs1 xs2 = half' xs (x1:xs1) (x2:xs2)
But if you want to create runs for merge sort, then create
sorted runs:
runs :: (Ord a) => [a] -> [[a]]
runs [] = []
runs (x:xs) = runs' xs x x (x:)
where
runs' [] _ _ k = [k []]
runs' (x:xs) lo hi k
| x < lo = runs' xs x hi ((x:) . k)
| x > hi = runs' xs lo x (k . (x:))
| otherwise = (k []) : runs' xs x x (x:)
Cheers,
Andrew Bromage
ZeD
>> half :: [a] -> ([a],[a])
>> half list = splitAt (length list `div` 2) list
> But beauty is in the eye of the beholder, and I thought the OP might
> appreciate Danvy's ideas since he indicated he was looking for
> "beauty", not "effficiency".
Onestly I find this solution the most beatiful (in the "pythonic" meaning of
beauty, if you know what I mean) I've found.
The "uglyness" in my original idea comed from that strange div replacement.
At the moment I'm not focused about efficency, just about readability.
--
Under construction
paolo....@gmail.com
> Try to use the list as an implicit counter:
This will also get the job done by doing the "implicit counting" at
the same time it's building the two halves.
half :: [a] -> ([a],[a])
half xs = halfiter xs xs
halfiter (x:xs) (_:_:ys) = let (xs',zs') = halfiter xs ys
in (x:xs',zs')
halfiter xs _ = ([], xs)
An additional rule (before the last)
halfiter (x:xs) [_] = ([x], xs)
will put the middle item in the first half if the list has an odd
number of elements.
Paolo (my first Haskell program ;-)