Proposal: Make GHC.Arr.listArray slightly stricter to allow fusion
Currently, GHC.Arr.listArray is pretty lazy: listArray (1,3) $ [1,2,3] ++ undefined will work perfectly fine. This is actually lazier than the current array: array (1,3) $ [(1,1), (2,2), (3,3)] ++ undefined = undefined Unfortunately, I don't think it's possible to make listArray fuse with a list producer while preserving quite that level of laziness. If we're willing to be slightly stricter, however, I think everything works. Specifically, I propose that we allow listArray (length xs) (xs ++ _|_) = _|_ The resulting listArray code is below. {-# INLINE mylistArray #-} listArray :: Ix i => (i,i) -> [e] -> Array i e listArray (l,u) es = runST (ST $ \s1# -> case safeRangeSize (l,u) of { n@(I# n#) -> case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> let fillFromList y r i# s3# | isTrue# (i# ==# n#) = s3# | otherwise = case writeArray# marr# i# y s3# of s4# -> r (i# +# 1#) s4# in case foldr fillFromList (\_ s# -> s#) es 0# s2# of s5# -> done l u n marr# s5# }})
Hi, Am Donnerstag, den 13.11.2014, 05:22 -0500 schrieb David Feuer:
Currently, GHC.Arr.listArray is pretty lazy:
listArray (1,3) $ [1,2,3] ++ undefined
will work perfectly fine.
This is actually lazier than the current array:
array (1,3) $ [(1,1), (2,2), (3,3)] ++ undefined = undefined
Unfortunately, I don't think it's possible to make listArray fuse with a list producer while preserving quite that level of laziness. If we're willing to be slightly stricter, however, I think everything works. Specifically, I propose that we allow
listArray (length xs) (xs ++ _|_) = _|_>
given that listArray (1,3) xs = listArray (1,3) (take 3 (xs)) and take can fuse with a good producer (can it?), I would expect that listArray can be made to fuse as good or as bad as take. What precisely is the problem with the more lazy listArray? Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
Oh, I think I am a fool! That'll show me to post to the list at such an
absurd hour.
On Thu, Nov 13, 2014 at 6:33 AM, Joachim Breitner
Hi,
Am Donnerstag, den 13.11.2014, 05:22 -0500 schrieb David Feuer:
Currently, GHC.Arr.listArray is pretty lazy:
listArray (1,3) $ [1,2,3] ++ undefined
will work perfectly fine.
This is actually lazier than the current array:
array (1,3) $ [(1,1), (2,2), (3,3)] ++ undefined = undefined
Unfortunately, I don't think it's possible to make listArray fuse with a list producer while preserving quite that level of laziness. If we're willing to be slightly stricter, however, I think everything works. Specifically, I propose that we allow
listArray (length xs) (xs ++ _|_) = _|_>
given that listArray (1,3) xs = listArray (1,3) (take 3 (xs)) and take can fuse with a good producer (can it?), I would expect that listArray can be made to fuse as good or as bad as take.
What precisely is the problem with the more lazy listArray?
Greetings, Joachim
-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
To be really specific, in case anyone can learn anything from me
embarrassing myself:
take uses a neat little trick to avoid blowing up on a bottom-terminated
list: instead of counting down to 0, it counts down to 1. This lets it stop
just short of trouble. The same technique should work for listArray.
On Nov 13, 2014 11:20 AM, "David Feuer"
Oh, I think I am a fool! That'll show me to post to the list at such an absurd hour.
On Thu, Nov 13, 2014 at 6:33 AM, Joachim Breitner < mail@joachim-breitner.de> wrote:
Hi,
Am Donnerstag, den 13.11.2014, 05:22 -0500 schrieb David Feuer:
Currently, GHC.Arr.listArray is pretty lazy:
listArray (1,3) $ [1,2,3] ++ undefined
will work perfectly fine.
This is actually lazier than the current array:
array (1,3) $ [(1,1), (2,2), (3,3)] ++ undefined = undefined
Unfortunately, I don't think it's possible to make listArray fuse with a list producer while preserving quite that level of laziness. If we're willing to be slightly stricter, however, I think everything works. Specifically, I propose that we allow
listArray (length xs) (xs ++ _|_) = _|_>
given that listArray (1,3) xs = listArray (1,3) (take 3 (xs)) and take can fuse with a good producer (can it?), I would expect that listArray can be made to fuse as good or as bad as take.
What precisely is the problem with the more lazy listArray?
Greetings, Joachim
-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
On 13-11-2014 14:54, David Feuer wrote:
To be really specific, in case anyone can learn anything from me embarrassing myself:
take uses a neat little trick to avoid blowing up on a bottom-terminated list: instead of counting down to 0, it counts down to 1. This lets it stop just short of trouble. The same technique should work for listArray.
Thanks for sharing! That's a nift trick. -- Felipe.
participants (3)
-
David Feuer -
Felipe Lessa -
Joachim Breitner