Mutable grid

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Mutable grid

Mike Houghton
Hi,

I’m looking a problem where I have an NxN grid of ints.
I need a function like setValue x y newVal

I have tried using [[Int]] but it does become messy when splitting , dropping and then ++ back together.

What other options are available to represent a mutable grid?

Many thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Michael Orlitzky
On 12/19/2016 08:10 AM, mike h wrote:

> Hi,
>
> I’m looking a problem where I have an NxN grid of ints. I need a
> function like setValue x y newVal
>
> I have tried using [[Int]] but it does become messy when splitting ,
> dropping and then ++ back together.
>
> What other options are available to represent a mutable grid?
>

Mutable vectors (from the vector[1] package) are an obvious choice. When
I had to do something similar, I wound up going all the way to repa[2],
which magically turns all of your grid operations into parallel ones.


[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/repa

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Mike Houghton
Thanks for the pointers - I’ll take a look.

The background to this is one of the puzzles on Advent Of Code 2016 Q.8.

There are (several hundred) sequential  operations on a grid 50 x 6  - initially all zeroes
e.g. 
rotate row y=0 by 4 
rect 2x1 — sets sub grid from (0,0) to (2,1) to all 1s
rotate column x=35 by 1

I’m fine about parsing the input to a data structure and executing them i.e. 

evalExpr :: Expr -> Screen -> Screen     — screen is essentially [[Int]]
evalExpr e s =
    case e of
        (Rect   r c ) ->     evalRect   r c s
        (RotRow r by) -> evalRotRow r by s
        (RotCol c by) -> evalRotCol c by s
        (NOP        ) -> id s

rotating a row was simple enough, code to  rotate column a bit untidy and not very nice. The 
evalRect  - which sets values to one in the rectangle of size r x c starting at (0,0) top left - triggered the original question.


At this point  my knowledge of Haskell is being pushed (which is good) but I have a feeling that 
my approach is not ‘correct’ once it gets beyond the parsing. Should each of the evalRect, evalRotRow and evalRotCol be called with a Screen (i.e. the grid at the root of this question)?
Is the state monad a fit for this problem?
Should I change my approach or is using vector the way forward?

Many thanks

Mike





On 19 Dec 2016, at 15:27, Michael Orlitzky <[hidden email]> wrote:

On 12/19/2016 08:10 AM, mike h wrote:
Hi,

I’m looking a problem where I have an NxN grid of ints. I need a
function like setValue x y newVal

I have tried using [[Int]] but it does become messy when splitting ,
dropping and then ++ back together.

What other options are available to represent a mutable grid?


Mutable vectors (from the vector[1] package) are an obvious choice. When
I had to do something similar, I wound up going all the way to repa[2],
which magically turns all of your grid operations into parallel ones.


[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/repa

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Michael Orlitzky
On 12/19/2016 01:31 PM, mike h wrote:

>
> There are (several hundred) sequential  operations on a grid 50 x 6
>  - initially all zeroes
> ...
>
> At this point  my knowledge of Haskell is being pushed (which is good)
> but I have a feeling that
> my approach is not ‘correct’ once it gets beyond the parsing. Should
> each of the evalRect, evalRotRow and evalRotCol be called with a Screen
> (i.e. the grid at the root of this question)?
> Is the state monad a fit for this problem?
> Should I change my approach or is using vector the way forward?
>

This is just plain difficult to do functionally, don't be discouraged.
Using mutable vectors is going to speed things up, but it isn't going to
simplify anything conceptually.

If I were you, I would start by making everything work slowly-but-safely
on a tiny grid, accessing (and checking) everything by indices. First,
write yourself a function that can modify one entry on the screen. Then,
using that, a function that can modify one row. Then implement the
matrix "transpose", and you get column operations for free: transpose,
do the thing for rows, and then transpose back.

Rather than evaluate the expressions at the same time you parse them, I
would convert them to functions instead. So the instruction "rect 3x2"
would get converted into a function that takes a Screen and outputs a
Screen. If you do that for all of the instructions, then you can just
compose everything. If "rect 3x2" gives you the function `f1` and "rect
5x7" gives you the function `f2`, then `f1 . f2` does one followed by
the other. Your program will wind up being one long composition of
functions that you can construct from the list of expressions. You can
compose an entire list of functions with a fold:

  ghci> let times n x = n*x
  ghci> let fs = [ times n | n <- [1..10] ]
  ghci> foldr (.) id fs 1     -- 10 times 9 times 8 times... times 1
  3628800

If you need it to be fast, then you can switch the list of lists to a
mutable vector of mutable vectors. All you should have to change is the
function that modifies one entry, since the rest will be implemented in
terms of that.

On the other hand, if it's already fast enough, it would be very sexy to
use something like fixed-vector to ensure that the row/column lengths
are statically checked =)

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Mike Houghton
Thanks Michael for you help. Very useful.

Mike

> On 19 Dec 2016, at 20:12, Michael Orlitzky <[hidden email]> wrote:
>
> On 12/19/2016 01:31 PM, mike h wrote:
>>
>> There are (several hundred) sequential  operations on a grid 50 x 6
>> - initially all zeroes
>> ...
>>
>> At this point  my knowledge of Haskell is being pushed (which is good)
>> but I have a feeling that
>> my approach is not ‘correct’ once it gets beyond the parsing. Should
>> each of the evalRect, evalRotRow and evalRotCol be called with a Screen
>> (i.e. the grid at the root of this question)?
>> Is the state monad a fit for this problem?
>> Should I change my approach or is using vector the way forward?
>>
>
> This is just plain difficult to do functionally, don't be discouraged.
> Using mutable vectors is going to speed things up, but it isn't going to
> simplify anything conceptually.
>
> If I were you, I would start by making everything work slowly-but-safely
> on a tiny grid, accessing (and checking) everything by indices. First,
> write yourself a function that can modify one entry on the screen. Then,
> using that, a function that can modify one row. Then implement the
> matrix "transpose", and you get column operations for free: transpose,
> do the thing for rows, and then transpose back.
>
> Rather than evaluate the expressions at the same time you parse them, I
> would convert them to functions instead. So the instruction "rect 3x2"
> would get converted into a function that takes a Screen and outputs a
> Screen. If you do that for all of the instructions, then you can just
> compose everything. If "rect 3x2" gives you the function `f1` and "rect
> 5x7" gives you the function `f2`, then `f1 . f2` does one followed by
> the other. Your program will wind up being one long composition of
> functions that you can construct from the list of expressions. You can
> compose an entire list of functions with a fold:
>
>  ghci> let times n x = n*x
>  ghci> let fs = [ times n | n <- [1..10] ]
>  ghci> foldr (.) id fs 1     -- 10 times 9 times 8 times... times 1
>  3628800
>
> If you need it to be fast, then you can switch the list of lists to a
> mutable vector of mutable vectors. All you should have to change is the
> function that modifies one entry, since the rest will be implemented in
> terms of that.
>
> On the other hand, if it's already fast enough, it would be very sexy to
> use something like fixed-vector to ensure that the row/column lengths
> are statically checked =)
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Magnus Therning
In reply to this post by Mike Houghton
How did it go?

When I solved that AoC problem I ended up using the matrix package: http://hackage.haskell.org/package/matrix

/M


On 19 Dec 2016 7:31 pm, "mike h" <[hidden email]> wrote:
Thanks for the pointers - I’ll take a look.

The background to this is one of the puzzles on Advent Of Code 2016 Q.8.

There are (several hundred) sequential  operations on a grid 50 x 6  - initially all zeroes
e.g. 
rotate row y=0 by 4 
rect 2x1 — sets sub grid from (0,0) to (2,1) to all 1s
rotate column x=35 by 1

I’m fine about parsing the input to a data structure and executing them i.e. 

evalExpr :: Expr -> Screen -> Screen     — screen is essentially [[Int]]
evalExpr e s =
    case e of
        (Rect   r c ) ->     evalRect   r c s
        (RotRow r by) -> evalRotRow r by s
        (RotCol c by) -> evalRotCol c by s
        (NOP        ) -> id s

rotating a row was simple enough, code to  rotate column a bit untidy and not very nice. The 
evalRect  - which sets values to one in the rectangle of size r x c starting at (0,0) top left - triggered the original question.


At this point  my knowledge of Haskell is being pushed (which is good) but I have a feeling that 
my approach is not ‘correct’ once it gets beyond the parsing. Should each of the evalRect, evalRotRow and evalRotCol be called with a Screen (i.e. the grid at the root of this question)?
Is the state monad a fit for this problem?
Should I change my approach or is using vector the way forward?

Many thanks

Mike





On 19 Dec 2016, at 15:27, Michael Orlitzky <[hidden email]> wrote:

On 12/19/2016 08:10 AM, mike h wrote:
Hi,

I’m looking a problem where I have an NxN grid of ints. I need a
function like setValue x y newVal

I have tried using [[Int]] but it does become messy when splitting ,
dropping and then ++ back together.

What other options are available to represent a mutable grid?


Mutable vectors (from the vector[1] package) are an obvious choice. When
I had to do something similar, I wound up going all the way to repa[2],
which magically turns all of your grid operations into parallel ones.


[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/repa

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Mutable grid

Mike Houghton
Hi,
In the end I used a set to hold tuples of int pairs (row, col) and manipulated them


type By = Int 
type Row = Int 
type Col = Int 

type Pixels = Set (Row, Col)

data Screen = Screen

  { maxX   :: Col,
    maxY   :: Row,
    pixels :: Pixels
  }

Thanks

Mike

On 24 Dec 2016, at 14:37, Magnus Therning <[hidden email]> wrote:

How did it go?

When I solved that AoC problem I ended up using the matrix package: http://hackage.haskell.org/package/matrix

/M


On 19 Dec 2016 7:31 pm, "mike h" <[hidden email]> wrote:
Thanks for the pointers - I’ll take a look.

The background to this is one of the puzzles on Advent Of Code 2016 Q.8.

There are (several hundred) sequential  operations on a grid 50 x 6  - initially all zeroes
e.g. 
rotate row y=0 by 4 
rect 2x1 — sets sub grid from (0,0) to (2,1) to all 1s
rotate column x=35 by 1

I’m fine about parsing the input to a data structure and executing them i.e. 

evalExpr :: Expr -> Screen -> Screen     — screen is essentially [[Int]]
evalExpr e s =
    case e of
        (Rect   r c ) ->     evalRect   r c s
        (RotRow r by) -> evalRotRow r by s
        (RotCol c by) -> evalRotCol c by s
        (NOP        ) -> id s

rotating a row was simple enough, code to  rotate column a bit untidy and not very nice. The 
evalRect  - which sets values to one in the rectangle of size r x c starting at (0,0) top left - triggered the original question.


At this point  my knowledge of Haskell is being pushed (which is good) but I have a feeling that 
my approach is not ‘correct’ once it gets beyond the parsing. Should each of the evalRect, evalRotRow and evalRotCol be called with a Screen (i.e. the grid at the root of this question)?
Is the state monad a fit for this problem?
Should I change my approach or is using vector the way forward?

Many thanks

Mike





On 19 Dec 2016, at 15:27, Michael Orlitzky <[hidden email]> wrote:

On 12/19/2016 08:10 AM, mike h wrote:
Hi,

I’m looking a problem where I have an NxN grid of ints. I need a
function like setValue x y newVal

I have tried using [[Int]] but it does become messy when splitting ,
dropping and then ++ back together.

What other options are available to represent a mutable grid?


Mutable vectors (from the vector[1] package) are an obvious choice. When
I had to do something similar, I wound up going all the way to repa[2],
which magically turns all of your grid operations into parallel ones.


[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/repa

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners