Fwd: Unexpected behaviour: foldAllP -- Order of arguments in calls to associative operator

18 views
Skip to first unread message

Víctor López Juan

unread,
Apr 27, 2014, 6:09:16 PM4/27/14
to haskel...@googlegroups.com
When applying foldP or foldAllP to a one-dimensional array, the element
with the highest index is passed as first argument, and the element
with the lowest index is passed as second argument.

For example, when running this code with the latest version of Repa
(repa-3.2.3.3):

module MinimalBug where

import Data.Array.Repa hiding ((++))
import Control.Monad.Identity

import System.IO.Unsafe

add :: Int -> Int -> Int
add a b = let c = a + b in
unsafePerformIO (putStrLn $ show a ++ " + " ++ show b ++ " = "
++ show c) `seq` c

example :: Int
example =
let v = fromListUnboxed (Z :. (10 :: Int)) [1..10] in
runIdentity $ foldAllP add 0 vs

… it produces the following output:

$> example
2 + 1 = 3
3 + 3 = 6
4 + 6 = 10
5 + 10 = 15
6 + 15 = 21
7 + 21 = 28
8 + 28 = 36
9 + 36 = 45
10 + 45 = 55
0 + 55 = 55
55

which corresponds to:
(0 `add` (10 `add` (9 `add` (8 `add` … (2 `add` 1)))))

instead of, for example, the following:

$> example
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
15 + 6 = 21
21 + 7 = 28
28 + 8 = 36
36 + 9 = 45
45 + 10 = 55
55 + 0 = 55
55

which corresponds to the expected:
(((1 `add` 2) `add` 3) `add` 4) … ) `add` 10) `add` 0)

=====

Is this behaviour intentional, or is it a bug?

In any case, I wouldn't suggest changing the implementation, as it might
break existing programs, and the alternative behaviour can be achieved
by applying flip to the operator.

However, perhaps it can be documented? I find the current behaviour
surprising, and it might be so for other users. I'm willing to submit a
patch to that effect.

-- Víctor












signature.asc

Ben Lippmeier

unread,
Apr 29, 2014, 6:55:04 AM4/29/14
to vic...@lopezjuan.com, haskel...@googlegroups.com

On 28 Apr 2014, at 8:09 , Víctor López Juan <vic...@lopezjuan.com> wrote:
>
> Is this behaviour intentional, or is it a bug?

I guess it's a bug. I've only ever used foldAllP with commutative operators, so the order didn't matter.


> In any case, I wouldn't suggest changing the implementation, as it might
> break existing programs, and the alternative behaviour can be achieved
> by applying flip to the operator.
>
> However, perhaps it can be documented? I find the current behaviour
> surprising, and it might be so for other users. I'm willing to submit a
> patch to that effect.

I'd be fine with a patch that both flipped the order and documented it. I don't see a reason to preserve broken behaviour between versions -- that's what version numbers are for.

Ben.

Víctor López Juan

unread,
May 5, 2014, 10:53:51 AM5/5/14
to Ben Lippmeier, haskel...@googlegroups.com
> I'd be fine with a patch that both flipped the order and documented
it. I don't see a reason to preserve broken behaviour between versions
-- that's what version numbers are for.

Ok. I'm busy right now, but i'll submit a thorough patch by mid June.

-- Víctor
signature.asc

Víctor López Juan

unread,
Jun 14, 2014, 6:32:03 PM6/14/14
to Ben Lippmeier, haskel...@googlegroups.com
Here's the patch. It flips the order, and includes some documentation
and examples which will show up in the docs for Data.Array.Repa.

-- Víctor

P.S.: It's hard to find examples where the order of reduction matters
without involving big data structures.
flip_order_and_document.patch
signature.asc
Reply all
Reply to author
Forward
0 new messages