Rewrite this imperative in FP way - Haskell-Cafe - Haskell.org

newer
ANN: Updated OpenGL libraries

Rewrite this imperative in FP way

older
Problem resolving: Hangman

Haisheng Wu

5 Feb 2012 5 Feb '12

1:28 a.m.

a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0] for i in b: for j in c: if (i+j)<3: d[i+j] += a[i] My just work implementation in Haskell http://hpaste.org/57452 Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358 Do you have any cool solution in FP way? Thanks. -Simon

Attachments:

attachment.html (text/html — 2.0 KB)

Reply

Sign in to reply online Use email software

Show replies by date

Roman Cheplyaka

5 Feb 5 Feb

4:20 a.m.

* Haisheng Wu [2012-02-05 14:28:10+0800]

a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

Do you have any cool solution in FP way?

You can use IntMap as a replacement for arrays: (I didn't understand your algorithm exactly, since you use 'c', which is not defined, but hopefully this is close enough) import Control.Monad import Data.List import Data.IntMap as IntMap a = [1,1,1,1] b = [0,1,2,3] c = IntMap.fromList $ zipWith (,) [0..] a d = foldl' f IntMap.empty $ liftM2 (,) a b where f m (i, j) = let s = i+j in if s < 3 then IntMap.insertWith (+) s (c ! i) m else m main = print d A single non-obvious thing here is "liftM2 (,) a b" -- it builds the cartesian product of lists a and b and is used here to replace your nested loops. -- Roman I. Cheplyaka :: http://ro-che.info/

Reply

Sign in to reply online Use email software

Jon Fairbairn

4:24 a.m.

Haisheng Wu writes:

a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i] Do you have any cool solution in FP way?

I find the above sufficiently alien that I can’t work out what it’s meant to do (what is it actually for?). c is undefined for one thing. But you might like to see what do i <- b; j <-c ; return (i,j) does and consider what “filter (< 3) . map (uncurry (+))” does, and possibly look at Data.Array.array, depending on what the problem you are trying to solve is. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk

Reply

Sign in to reply online Use email software

Haisheng Wu

10:36 a.m.

Sorry there is a mistake in the problem description. Here it is in Python: a = [1,1,1,1] b = [0,1,2,3] c = [0,2] d = [0,0,0,0] for i in b: for j in c: if (i+j)<3: d[i+j] += a[i] -Haisheng On Sun, Feb 5, 2012 at 2:28 PM, Haisheng Wu wrote:

a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

Reply

Sign in to reply online Use email software

Morel Pisum

10:42 a.m.

"+= a[i]" is the same as "+=1", isn't it? (i accidentally didn't reply to the list on my first try. sorry.) Am 05.02.2012 16:36, schrieb Haisheng Wu:

Sorry there is a mistake in the problem description. Here it is in Python:

a = [1,1,1,1] b = [0,1,2,3] c = [0,2] d = [0,0,0,0] for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

-Haisheng

On Sun, Feb 5, 2012 at 2:28 PM, Haisheng Wu wrote:

...
a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Mike Burns

10:42 a.m.

Can you write it as a Python function? Another way of asking: is the goal to mutate d or is it to produce the list? On 2012-02-05 23.36.28 +0800, Haisheng Wu wrote:

Sorry there is a mistake in the problem description. Here it is in Python:

a = [1,1,1,1] b = [0,1,2,3] c = [0,2] d = [0,0,0,0] for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

-Haisheng

On Sun, Feb 5, 2012 at 2:28 PM, Haisheng Wu wrote:

...
a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Matthew Farkas-Dyck

12:57 p.m.

On Sun, Feb 5, 2012 at 2:28 PM, Haisheng Wu wrote:

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

Do you have any cool solution in FP way?

Not sure whether this is cool, but here it is nonetheless: a = repeat 1; b = [0..3]; c = [0,2]; d = map (sum ∘ map ((a !!) ∘ fromIntegral) ∘ ($ (filter (<3) ∘ map sum ∘ sequence) [b,c]) ∘ filter ∘ (≡)) [1..];

Reply

Sign in to reply online Use email software

Yves Parès

10:37 a.m.

Concerning your first solution, I don't understand why you redefine Eq but not Ord instance. Ord will still work by comparing the tuples and not the first elements of said tuples. Plus the good news is you don't have to do this: just use regular tuples and use sort*By *or group*By *functions from Data.List with the 'on' function from Data.Function. For instance your Eq instance could have been written x == y = (==) `on` (fst . getTuple) With regular tuples you can write "sortBy (compare `on` fst)". Plus can you rewrite your original imperative algorithm with the right variable names? You're using a 'd' array that's not been defined. 2012/2/5 Haisheng Wu

a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Yves Parès

10:39 a.m.

For instance your Eq instance could have been written x == y = (==) `on` (fst . getTuple)

Sorry, wrong arity: (==) = (==) `on` (fst . getTuple) Okay for the imperative code. 2012/2/5 Yves Parès

Concerning your first solution, I don't understand why you redefine Eq but not Ord instance. Ord will still work by comparing the tuples and not the first elements of said tuples. Plus the good news is you don't have to do this: just use regular tuples and use sort*By *or group*By *functions from Data.List with the 'on' function from Data.Function. For instance your Eq instance could have been written x == y = (==) `on` (fst . getTuple)

With regular tuples you can write "sortBy (compare `on` fst)".

Plus can you rewrite your original imperative algorithm with the right variable names? You're using a 'd' array that's not been defined.

2012/2/5 Haisheng Wu

...
a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Haisheng Wu

6 Feb 6 Feb

5:56 a.m.

The reason I redefined Eq is: When doing `union` over two list of MyTuple is just base on its first element. Basically it means: [(1,2), (2,2)] `union` [(1,0), (2,0), (0,0)] produce [(1,2), (2,2), (0,0)] rather than [(1,2),(2,2),(1,0),(2,0),(0,0)] by default. -Haisheng On Sun, Feb 5, 2012 at 11:37 PM, Yves Parès wrote:

Concerning your first solution, I don't understand why you redefine Eq but not Ord instance. Ord will still work by comparing the tuples and not the first elements of said tuples. Plus the good news is you don't have to do this: just use regular tuples and use sort*By *or group*By *functions from Data.List with the 'on' function from Data.Function. For instance your Eq instance could have been written x == y = (==) `on` (fst . getTuple)

With regular tuples you can write "sortBy (compare `on` fst)".

Plus can you rewrite your original imperative algorithm with the right variable names? You're using a 'd' array that's not been defined.

2012/2/5 Haisheng Wu

...
a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Yves Parès

6:41 a.m.

Okay. But that's misleading, as normally x == y = True *iff* compare x y = EQ, but there this is not verified, as you don't redefined A function like "unionBy" doesn't exist, so IMHO to limit ambiguity, it would be a good idea to use MyTuple *only *at the specific place where you need its Eq instance instead of that of tuple (and then remove the Ord MyTuple instance), and use regular tuples elsewhere. The following should do the job: map getTuple . (`union` c) . map MyTuple 2012/2/6 Haisheng Wu

The reason I redefined Eq is: When doing `union` over two list of MyTuple is just base on its first element. Basically it means: [(1,2), (2,2)] `union` [(1,0), (2,0), (0,0)] produce [(1,2), (2,2), (0,0)] rather than [(1,2),(2,2),(1,0),(2,0),(0,0)] by default.

-Haisheng

On Sun, Feb 5, 2012 at 11:37 PM, Yves Parès wrote:

...
Concerning your first solution, I don't understand why you redefine Eq but not Ord instance. Ord will still work by comparing the tuples and not the first elements of said tuples. Plus the good news is you don't have to do this: just use regular tuples and use sort*By *or group*By *functions from Data.List with the 'on' function from Data.Function. For instance your Eq instance could have been written x == y = (==) `on` (fst . getTuple)

With regular tuples you can write "sortBy (compare `on` fst)".

Plus can you rewrite your original imperative algorithm with the right variable names? You're using a 'd' array that's not been defined.

2012/2/5 Haisheng Wu

...
a = [1,1,1,1] b = [0,1,2,3] d = [0,0,0,0]

for i in b: for j in c: if (i+j)<3: d[i+j] += a[i]

My just work implementation in Haskell http://hpaste.org/57452

Another people implementation in Haskell with Monad and it turns out complex and very imperatively. http://hpaste.org/57358

Do you have any cool solution in FP way?

Thanks. -Simon

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

4853

Age (days ago)

4854

Last active (days ago)

Download

10 comments

7 participants

tags

participants (7)

Haisheng Wu
Jon Fairbairn
Matthew Farkas-Dyck
Mike Burns
Morel Pisum
Roman Cheplyaka
Yves Parès