Re: [Haskell-cafe] Is there a nicer way to do this?
Don Stewart <[EMAIL PROTECTED]> writes: >>> splitAt n xs = (take n xs, drop n xs) >> Thanks. That is odd, though. It makes me wonder what to expect re >> optimization. Would the compiler/runtime know that splitAt could be >> done in a single pass? > Not with that definition. It would require some moderately unusual fusion > combining the take and drop into a single fold with the (,) on the inside, > rather than on the outside. Uhm, but I'm quite sure I saw a paper about how the garbage collector could discover this, and update both thunks simultaneously. (Unfortunately, I can't seem to find it now.) -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a nicer way to do this?
mfeathers: > Don Stewart wrote: > >mfeathers: > >> > >>segment :: Int -> [a] -> [[a]] > >>segment 0 _ = [] > >>segment _ [] = [] > >>segment n x = (take n x) : segment n (drop n x) > > > >The first set of parens can go, > > > > segment n x = take n x : segment n (drop n x) > > > >>I did a version of this which used splitAt but I wasn't sure whether it > >>was going to buy me anything re performance that would justify its > >>ugliness. > > > >Besides, > > > > splitAt n xs = (take n xs, drop n xs) > > Thanks. That is odd, though. It makes me wonder what to expect re > optimization. Would the compiler/runtime know that splitAt could be > done in a single pass? Not with that definition. It would require some moderately unusual fusion combining the take and drop into a single fold with the (,) on the inside, rather than on the outside. However, GHC actually implements splitAt as: splitAt (I n) ls | n < 0 = ([], ls) | otherwise = splitAt' n ls where splitAt' :: Int -> [a] -> ([a], [a]) splitAt' 0 xs = ([], xs) splitAt' _ [EMAIL PROTECTED] = (xs, xs) splitAt' m (x:xs) = (x:xs', xs'') where (xs', xs'') = splitAt' (m - 1) xs So there may be some benefit. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a nicer way to do this?
On Sun, Jul 6, 2008 at 5:25 PM, John Hamilton <[EMAIL PROTECTED]> wrote: > On Sun, Jul 6, 2008 at 16:45, Michael Feathers <[EMAIL PROTECTED]> wrote: >> >> >> segment :: Int -> [a] -> [[a]] >> segment 0 _ = [] >> segment _ [] = [] >> segment n x = (take n x) : segment n (drop n x) >> >> >> I did a version of this which used splitAt but I wasn't sure whether it was >> going to buy me anything re performance that would justify its ugliness. > > You can use > > segment n = takeWhile (not . null) . unfoldr (Just . splitAt n) > > I don't know how it compares in performance. It's from > http://www.haskell.org/haskellwiki/Blow_your_mind Watch out for negative numbers, though. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a nicer way to do this?
On Sun, Jul 6, 2008 at 16:45, Michael Feathers <[EMAIL PROTECTED]> wrote: > > > segment :: Int -> [a] -> [[a]] > segment 0 _ = [] > segment _ [] = [] > segment n x = (take n x) : segment n (drop n x) > > > I did a version of this which used splitAt but I wasn't sure whether it was > going to buy me anything re performance that would justify its ugliness. You can use segment n = takeWhile (not . null) . unfoldr (Just . splitAt n) I don't know how it compares in performance. It's from http://www.haskell.org/haskellwiki/Blow_your_mind - John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a nicer way to do this?
mfeathers: > > > segment :: Int -> [a] -> [[a]] > segment 0 _ = [] > segment _ [] = [] > segment n x = (take n x) : segment n (drop n x) The first set of parens can go, segment n x = take n x : segment n (drop n x) > > I did a version of this which used splitAt but I wasn't sure whether it > was going to buy me anything re performance that would justify its ugliness. Besides, splitAt n xs = (take n xs, drop n xs) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
