28 Nov 2012 18:57

## computation over containers, greatly simplified notation.

Dear all,

I came up with an idea to greatly simplify some kinds of array computations. It should work well with many kinds of arrays. Is this new?

https://gist.github.com/4162375

These few days, I've been trying to rewrite a hydrodynamic simulation code that used Data.Vector (~250 lines), to Repa [1] . It seemed promising, but soon I realized that I needed to use Repa.map and Repa.zipWith almost everywhere. I need careful thinking to transform every lines (that used vector's indexing) to Repa's point-free stile. Is there any better ways?

Then I realized that I was the author of Paraiso [2], a DSL for stencil computation. One of its feature is to write down array computation just as if it were scalar computation.

Basically what I need is ZipList-like Applicative instances for vectors and Repa arrays. Why not they support ZipVector? Because 'pure' of zipList was an infinite list and you can't do infinite vectors. Then I came up with this idea.

https://gist.github.com/4162375

the wrapper W does several things: it represents the 'pure,' homogeneous array in a space-efficient manner, and also serves as a newtype-wrapper of Num (and possibly Fractional, Floating...) instances.

Questions are: is this technology new? or promising? doomed?
It seems to me like a free-Applicative, like the free-Monad theory. Are they related?
The function 'backend' helps to mix in the non-zip-like computations. How can we remove the 'undefined' in the 'backend?'
Some of Repa computations are Monads. W needs to be a monad transformer to incooperate this.

Also I'm grateful to past cafe discussion on existing Zippable implementations [3][4] .

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

```_______________________________________________
```
1 Dec 2012 01:43

### Re: computation over containers, greatly simplified notation.

Dear everyone,

After a number of attempts [1] I'm starting to think that my initial approach was ill-directed.

After all, Functor, Applicative, Zip are three different classes.
Functors are type constructors where you can map unary functions over them.
Applicatives are those with map-over of zero-ary functions (pure,) unary functions, binary functions, ternary functions, ... etc.
Zip are those with unary, binary, ternary ... mapover, but not zero-ary map-over.

Repa Arrays and Vectors belong to Zip because there's no trivial unique way to implement pure.

What the customer really needed [2] seems to be the following series of functions:

forLiftZ1 :: Zip f => f a -> (a -> b) -> f b
forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c
forLiftZ3
:: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f d
Now I'm trying if it's possible to implement the series in a single shot [3] .

I'm reporting my progress for anyone who might be still thinking for me. Thank you!!

[1] https://github.com/nushio3/practice/tree/master/free-objects
[2] http://www.projectcartoon.com/cartoon/3
[3] https://github.com/nushio3/practice/blob/master/free-objects/printf6.hs

2012/11/29 Takayuki Muranushi
Dear all,

I came up with an idea to greatly simplify some kinds of array computations. It should work well with many kinds of arrays. Is this new?

https://gist.github.com/4162375

These few days, I've been trying to rewrite a hydrodynamic simulation code that used Data.Vector (~250 lines), to Repa [1] . It seemed promising, but soon I realized that I needed to use Repa.map and Repa.zipWith almost everywhere. I need careful thinking to transform every lines (that used vector's indexing) to Repa's point-free stile. Is there any better ways?

Then I realized that I was the author of Paraiso [2], a DSL for stencil computation. One of its feature is to write down array computation just as if it were scalar computation.

Basically what I need is ZipList-like Applicative instances for vectors and Repa arrays. Why not they support ZipVector? Because 'pure' of zipList was an infinite list and you can't do infinite vectors. Then I came up with this idea.

https://gist.github.com/4162375

the wrapper W does several things: it represents the 'pure,' homogeneous array in a space-efficient manner, and also serves as a newtype-wrapper of Num (and possibly Fractional, Floating...) instances.

Questions are: is this technology new? or promising? doomed?
It seems to me like a free-Applicative, like the free-Monad theory. Are they related?
The function 'backend' helps to mix in the non-zip-like computations. How can we remove the 'undefined' in the 'backend?'
Some of Repa computations are Monads. W needs to be a monad transformer to incooperate this.

Also I'm grateful to past cafe discussion on existing Zippable implementations [3][4] .

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
```_______________________________________________
```
1 Dec 2012 04:00

### Re: computation over containers, greatly simplified notation.

You might find this paper an interesting read: http://www.brics.dk/RS/01/10/

On Fri, Nov 30, 2012 at 4:43 PM, Takayuki Muranushi wrote:
Dear everyone,

After a number of attempts [1] I'm starting to think that my initial approach was ill-directed.

After all, Functor, Applicative, Zip are three different classes.
Functors are type constructors where you can map unary functions over them.
Applicatives are those with map-over of zero-ary functions (pure,) unary functions, binary functions, ternary functions, ... etc.
Zip are those with unary, binary, ternary ... mapover, but not zero-ary map-over.

Repa Arrays and Vectors belong to Zip because there's no trivial unique way to implement pure.

What the customer really needed [2] seems to be the following series of functions:
forLiftZ1 :: Zip f => f a -> (a -> b) -> f b
forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c
forLiftZ3
:: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f d
Now I'm trying if it's possible to implement the series in a single shot [3] .

I'm reporting my progress for anyone who might be still thinking for me. Thank you!!

[1] https://github.com/nushio3/practice/tree/master/free-objects
[2] http://www.projectcartoon.com/cartoon/3
[3] https://github.com/nushio3/practice/blob/master/free-objects/printf6.hs

2012/11/29 Takayuki Muranushi
Dear all,

I came up with an idea to greatly simplify some kinds of array computations. It should work well with many kinds of arrays. Is this new?

https://gist.github.com/4162375

These few days, I've been trying to rewrite a hydrodynamic simulation code that used Data.Vector (~250 lines), to Repa [1] . It seemed promising, but soon I realized that I needed to use Repa.map and Repa.zipWith almost everywhere. I need careful thinking to transform every lines (that used vector's indexing) to Repa's point-free stile. Is there any better ways?

Then I realized that I was the author of Paraiso [2], a DSL for stencil computation. One of its feature is to write down array computation just as if it were scalar computation.

Basically what I need is ZipList-like Applicative instances for vectors and Repa arrays. Why not they support ZipVector? Because 'pure' of zipList was an infinite list and you can't do infinite vectors. Then I came up with this idea.

https://gist.github.com/4162375

the wrapper W does several things: it represents the 'pure,' homogeneous array in a space-efficient manner, and also serves as a newtype-wrapper of Num (and possibly Fractional, Floating...) instances.

Questions are: is this technology new? or promising? doomed?
It seems to me like a free-Applicative, like the free-Monad theory. Are they related?
The function 'backend' helps to mix in the non-zip-like computations. How can we remove the 'undefined' in the 'backend?'
Some of Repa computations are Monads. W needs to be a monad transformer to incooperate this.

Also I'm grateful to past cafe discussion on existing Zippable implementations [3][4] .

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

_______________________________________________

```_______________________________________________
```
1 Dec 2012 11:26

### Re: computation over containers, greatly simplified notation.

Thank you Jason, I have implemented those. https://github.com/nushio3/practice/blob/master/free-objects/zipn-03.hs

I implemented what I have wanted. It is "forZN" in the following code.

https://github.com/nushio3/practice/blob/master/free-objects/zipf-05.hs

"forZN", much like "printf", can be used in place of any of the following functions.

forLiftZ1 :: Zip f => f a -> (a -> b) -> f b forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c forLiftZ3 :: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f d
...and more...

The last example in above code is the usecase of forZN in my mind: to zip several arrays with a long lambda. This pattern occurs frequently in my codes.

One drawback of current approach is that we need verbose type annotations like
" :: V.Vector String" in   "print \$ (forZN vd1 vc1 vi1 f_dci_s :: V.Vector String) ".

Maybe this is because PType carries insufficient type-level information, compared to Reduce and Insert. Now I'm now wondering if we can use ghc-7.6.1's rich kind features such as type-level lists to remove those verbose type annotations.

2012/12/1 Jason Dagit
You might find this paper an interesting read: http://www.brics.dk/RS/01/10/

On Fri, Nov 30, 2012 at 4:43 PM, Takayuki Muranushi wrote:
Dear everyone,

After a number of attempts [1] I'm starting to think that my initial approach was ill-directed.

After all, Functor, Applicative, Zip are three different classes.
Functors are type constructors where you can map unary functions over them.
Applicatives are those with map-over of zero-ary functions (pure,) unary functions, binary functions, ternary functions, ... etc.
Zip are those with unary, binary, ternary ... mapover, but not zero-ary map-over.

Repa Arrays and Vectors belong to Zip because there's no trivial unique way to implement pure.

What the customer really needed [2] seems to be the following series of functions:
forLiftZ1 :: Zip f => f a -> (a -> b) -> f b
forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c
forLiftZ3
:: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f d
Now I'm trying if it's possible to implement the series in a single shot [3] .

I'm reporting my progress for anyone who might be still thinking for me. Thank you!!

[1] https://github.com/nushio3/practice/tree/master/free-objects
[2] http://www.projectcartoon.com/cartoon/3
[3] https://github.com/nushio3/practice/blob/master/free-objects/printf6.hs

2012/11/29 Takayuki Muranushi
Dear all,

I came up with an idea to greatly simplify some kinds of array computations. It should work well with many kinds of arrays. Is this new?

https://gist.github.com/4162375

These few days, I've been trying to rewrite a hydrodynamic simulation code that used Data.Vector (~250 lines), to Repa [1] . It seemed promising, but soon I realized that I needed to use Repa.map and Repa.zipWith almost everywhere. I need careful thinking to transform every lines (that used vector's indexing) to Repa's point-free stile. Is there any better ways?

Then I realized that I was the author of Paraiso [2], a DSL for stencil computation. One of its feature is to write down array computation just as if it were scalar computation.

Basically what I need is ZipList-like Applicative instances for vectors and Repa arrays. Why not they support ZipVector? Because 'pure' of zipList was an infinite list and you can't do infinite vectors. Then I came up with this idea.

https://gist.github.com/4162375

the wrapper W does several things: it represents the 'pure,' homogeneous array in a space-efficient manner, and also serves as a newtype-wrapper of Num (and possibly Fractional, Floating...) instances.

Questions are: is this technology new? or promising? doomed?
It seems to me like a free-Applicative, like the free-Monad theory. Are they related?
The function 'backend' helps to mix in the non-zip-like computations. How can we remove the 'undefined' in the 'backend?'
Some of Repa computations are Monads. W needs to be a monad transformer to incooperate this.

Also I'm grateful to past cafe discussion on existing Zippable implementations [3][4] .

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

_______________________________________________

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
```_______________________________________________
```
1 Dec 2012 14:47

### Re: computation over containers, greatly simplified notation.

```Dear all,

https://github.com/nushio3/practice/blob/master/free-objects/zipf-12.hs

I was finally able to remove the verbose type annotations.

The point was (1) to let the argument-list carry the type-constructor
information, so that only values of the type (v a) can enter the
heterogeneous list;

data Cons (v :: * -> *) a b = Cons a b deriving (Eq, Show)
data Nil  (v :: * -> *)     = Nil      deriving (Eq, Show)

(2) to change the remainder of the program accordingly, and (3) to add
the following subtle modification, because instance finder does not
attempt to match unknown type a0 to "v result", but it does so to
"result."

class Reduce v f vxS result vyS | v f vxS -> result vyS where
reduce :: v f -> vxS -> (v result, vyS)
↓
class Reduce v f vxS result vyS | v f vxS -> result vyS where
reduce :: v f -> vxS -> (result, vyS)

Other samples work with modest type annotations.
https://github.com/nushio3/practice/blob/master/free-objects/zipf-13.hs

2012/12/1 Takayuki Muranushi <muranushi <at> gmail.com>
>
> Thank you Jason, I have implemented those. https://github.com/nushio3/practice/blob/master/free-objects/zipn-03.hs
>
> I implemented what I have wanted. It is "forZN" in the following code.
>
> https://github.com/nushio3/practice/blob/master/free-objects/zipf-05.hs
>
> "forZN", much like "printf", can be used in place of any of the following functions.
>
> forLiftZ1 :: Zip f => f a -> (a -> b) -> f b
> forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c
> forLiftZ3 :: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f
> d
>
> ...and more...
>
>
> The last example in above code is the usecase of forZN in my mind: to zip several arrays with a long lambda.
This pattern occurs frequently in my codes.
>
> One drawback of current approach is that we need verbose type annotations like
> " :: V.Vector String" in   "print \$ (forZN vd1 vc1 vi1 f_dci_s :: V.Vector String) ".
>
> Maybe this is because PType carries insufficient type-level information, compared to Reduce and
Insert. Now I'm now wondering if we can use ghc-7.6.1's rich kind features such as type-level lists to
remove those verbose type annotations.
>
>
>
>
>
> 2012/12/1 Jason Dagit <dagitj <at> gmail.com>
>>
>> You might find this paper an interesting read: http://www.brics.dk/RS/01/10/
>>
>> On Fri, Nov 30, 2012 at 4:43 PM, Takayuki Muranushi <muranushi <at> gmail.com> wrote:
>>>
>>> Dear everyone,
>>>
>>> After a number of attempts [1] I'm starting to think that my initial approach was ill-directed.
>>>
>>> After all, Functor, Applicative, Zip are three different classes.
>>> Functors are type constructors where you can map unary functions over them.
>>> Applicatives are those with map-over of zero-ary functions (pure,) unary functions, binary
functions, ternary functions, ... etc.
>>> Zip are those with unary, binary, ternary ... mapover, but not zero-ary map-over.
>>>
>>> Repa Arrays and Vectors belong to Zip because there's no trivial unique way to implement pure.
>>>
>>> What the customer really needed [2] seems to be the following series of functions:
>>>
>>>
>>> forLiftZ1 :: Zip f => f a -> (a -> b) -> f b
>>>
>>>
>>>
>>>
>>> forLiftZ2 :: Zip f => f a -> f b -> (a -> b -> c) -> f c
>>>
>>>
>>>
>>>
>>>
>>> forLiftZ3 :: Zip f => f a -> f b -> f c -> (a -> b -> c -> d) -> f d
>>>
>>>
>>>
>>>
>>>
>>> Now I'm trying if it's possible to implement the series in a single shot [3] .
>>>
>>> I'm reporting my progress for anyone who might be still thinking for me. Thank you!!
>>>
>>> [1] https://github.com/nushio3/practice/tree/master/free-objects
>>> [2] http://www.projectcartoon.com/cartoon/3
>>> [3] https://github.com/nushio3/practice/blob/master/free-objects/printf6.hs
>>>
>>>
>>>
>>>
>>> 2012/11/29 Takayuki Muranushi <muranushi <at> gmail.com>
>>>>
>>>> Dear all,
>>>>
>>>> I came up with an idea to greatly simplify some kinds of array computations. It should work well with
many kinds of arrays. Is this new?
>>>>
>>>> https://gist.github.com/4162375
>>>>
>>>>
>>>>
>>>> These few days, I've been trying to rewrite a hydrodynamic simulation code that used Data.Vector
(~250 lines), to Repa [1] . It seemed promising, but soon I realized that I needed to use Repa.map and
Repa.zipWith almost everywhere. I need careful thinking to transform every lines (that used vector's
indexing) to Repa's point-free stile. Is there any better ways?
>>>>
>>>> Then I realized that I was the author of Paraiso [2], a DSL for stencil computation. One of its feature is
to write down array computation just as if it were scalar computation.
>>>>
>>>> Basically what I need is ZipList-like Applicative instances for vectors and Repa arrays. Why not they
support ZipVector? Because 'pure' of zipList was an infinite list and you can't do infinite vectors. Then
I came up with this idea.
>>>>
>>>> https://gist.github.com/4162375
>>>>
>>>> the wrapper W does several things: it represents the 'pure,' homogeneous array in a space-efficient
manner, and also serves as a newtype-wrapper of Num (and possibly Fractional, Floating...) instances.
>>>>
>>>> Questions are: is this technology new? or promising? doomed?
>>>> It seems to me like a free-Applicative, like the free-Monad theory. Are they related?
>>>> The function 'backend' helps to mix in the non-zip-like computations. How can we remove the
'undefined' in the 'backend?'
>>>> Some of Repa computations are Monads. W needs to be a monad transformer to incooperate this.
>>>>
>>>> Also I'm grateful to past cafe discussion on existing Zippable implementations [3][4] .
>>>>
>>>>
>>>>
>>>> --
>>>> Takayuki MURANUSHI
>>>> The Hakubi Center for Advanced Research, Kyoto University
>>>> http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
>>>
>>>
>>>
>>>
>>> --
>>> Takayuki MURANUSHI
>>> The Hakubi Center for Advanced Research, Kyoto University
>>> http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
>>>
>>> _______________________________________________
>>>
>>
>
>
>
> --
> Takayuki MURANUSHI
> The Hakubi Center for Advanced Research, Kyoto University
> http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

--
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

_______________________________________________