Quantcast

functional/immutable programming question

classic Classic list List threaded Threaded
132 messages Options
1234 ... 7
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

functional/immutable programming question

HamsterofDeath
in pure functional programming, there are no side effects. this means, the only "effect" a method has is its returned value, right? it doesn't hold a mutable state.

if so, how do i implement something that HAS to hold a state? what if let's say 10 clients try to add elements to the same list instance? there has to be a managing class that holds the list, right?


--
GMX DSL Doppel-Flat ab 19,99 €/mtl.! Jetzt auch mit
gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

HamsterofDeath
if every client just gets the current list and adds an element, i'll have a "hydra" (list with many heads and one tail), so as far as i understand it there has to be some state in the program where the new head replaced the old head. otherwise, the second caller has no way to access the current head of the list, it'll just get the initial one.

-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 10:45:52 +0100
> Von: "Dennis Haupt" <[hidden email]>
> An: [hidden email]
> Betreff: [scala-user] functional/immutable programming question

> in pure functional programming, there are no side effects. this means, the
> only "effect" a method has is its returned value, right? it doesn't hold a
> mutable state.
>
> if so, how do i implement something that HAS to hold a state? what if
> let's say 10 clients try to add elements to the same list instance? there has
> to be a managing class that holds the list, right?
>
>
> --
> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl

--
Ihr GMX Postfach immer dabei: die kostenlose GMX Mail App für Android.
Komfortabel, sicher und schnell: www.gmx.de/android
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Robert Wills-2
In reply to this post by HamsterofDeath
In a pure language the 'something' holding the state would be a state
or writer monad.

Of course if this were a proper client-server environment you would
need to have some impurity or else your program would never be able to
handle non-determinism.

-Rob

On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> in pure functional programming, there are no side effects. this means, the only "effect" a method has is its returned value, right? it doesn't hold a mutable state.
>
> if so, how do i implement something that HAS to hold a state? what if let's say 10 clients try to add elements to the same list instance? there has to be a managing class that holds the list, right?
>
>
> --
> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

HamsterofDeath
what is a state monad?

-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 09:53:56 +0000
> Von: Robert Wills <[hidden email]>
> An: Dennis Haupt <[hidden email]>
> CC: [hidden email]
> Betreff: Re: [scala-user] functional/immutable programming question

> In a pure language the 'something' holding the state would be a state
> or writer monad.
>
> Of course if this were a proper client-server environment you would
> need to have some impurity or else your program would never be able to
> handle non-determinism.
>
> -Rob
>
> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> > in pure functional programming, there are no side effects. this means,
> the only "effect" a method has is its returned value, right? it doesn't hold
> a mutable state.
> >
> > if so, how do i implement something that HAS to hold a state? what if
> let's say 10 clients try to add elements to the same list instance? there has
> to be a managing class that holds the list, right?
> >
> >
> > --
> > GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
> >

--
GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Razvan Cojocaru-2
It's like the IO monad but a little different ;)

Thanks,
Razvan

On 2010-11-11, at 5:00 AM, "Dennis Haupt" <[hidden email]> wrote:

> what is a state monad?
>
> -------- Original-Nachricht --------
>> Datum: Thu, 11 Nov 2010 09:53:56 +0000
>> Von: Robert Wills <[hidden email]>
>> An: Dennis Haupt <[hidden email]>
>> CC: [hidden email]
>> Betreff: Re: [scala-user] functional/immutable programming question
>
>> In a pure language the 'something' holding the state would be a state
>> or writer monad.
>>
>> Of course if this were a proper client-server environment you would
>> need to have some impurity or else your program would never be able to
>> handle non-determinism.
>>
>> -Rob
>>
>> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
>>> in pure functional programming, there are no side effects. this means,
>> the only "effect" a method has is its returned value, right? it doesn't hold
>> a mutable state.
>>>
>>> if so, how do i implement something that HAS to hold a state? what if
>> let's say 10 clients try to add elements to the same list instance? there has
>> to be a managing class that holds the list, right?
>>>
>>>
>>> --
>>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
>>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
>>>
>
> --
> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
Razvan Cojocaru,
Work: http://www.sigma-systems.com
Playground: http://wiki.homecloud.ca
Latest cool toys: Scripster and Gremlins
Follow me: RSS Feed, Twitter, GitHub.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Sc iss
In reply to this post by HamsterofDeath
fp and immutable data structures are celebrated as solving all problems, but as you see, they don't, in particular they have no clear concept of dynamicity, so things that change over time. they don't solve your problem of concurrent access here, so you will need to linearize your clients in some way. for example, you could manage them with an Actor or use an STM... immutable structures and STM play nicely together, as when a transaction is aborted you haven't crippled your data structure, just the newly created copy (old list plus new head element, for instance) isn't stored in the ref, no damage is done.

best, -sciss-


Am 11.11.2010 um 09:45 schrieb Dennis Haupt:

> in pure functional programming, there are no side effects. this means, the only "effect" a method has is its returned value, right? it doesn't hold a mutable state.
>
> if so, how do i implement something that HAS to hold a state? what if let's say 10 clients try to add elements to the same list instance? there has to be a managing class that holds the list, right?
>
>
> --
> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Andreas Flierl

Sciss <[hidden email]> wrote:
> fp and immutable data structures are celebrated as solving all
> problems, but as you see, they don't, in particular they have no clear
> concept of dynamicity, so things that change over time.
> (snip)

Uhm, those monads sure look like a clear concept of dynamicity to me.
You might not like them, but that's a different story.

Kind regards
Andreas
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Robert Wills-2
In reply to this post by Sc iss
sciss is right.  Pure fp doesn't solve all your problems and there is
inevitably going to be some point of your program which is impure.
Things like the State monad help ensure that that purity is isolated
in one part of your program.  Haskell programs generally keep all the
'dynamic' or non-deterministic stuff in one part of the program by
using a stack of monads and other pointy-headed stuff.  Arguably, this
can make them hard to understand but it does make them very safe and
very easily testable.

I'm not sure if I'm on top of all the terminology or the concepts but
I think there are two issues here: one is purity and the other is
concurrency.  STM and actors help with the latter.  Monads help with
the former.

Thinking again about the example you describe the STM and actors would
be more useful there -- actors for handling the clients and stm for
handling access to  the list.  If however you had a complicated
computation that needed to manipulate some common piece of data you
could use a state monad there to provide pure access to the data
without having to thread the state through your entire computation.

-Rob

On Thu, Nov 11, 2010 at 12:30 PM, Sciss <[hidden email]> wrote:

> fp and immutable data structures are celebrated as solving all problems, but as you see, they don't, in particular they have no clear concept of dynamicity, so things that change over time. they don't solve your problem of concurrent access here, so you will need to linearize your clients in some way. for example, you could manage them with an Actor or use an STM... immutable structures and STM play nicely together, as when a transaction is aborted you haven't crippled your data structure, just the newly created copy (old list plus new head element, for instance) isn't stored in the ref, no damage is done.
>
> best, -sciss-
>
>
> Am 11.11.2010 um 09:45 schrieb Dennis Haupt:
>
>> in pure functional programming, there are no side effects. this means, the only "effect" a method has is its returned value, right? it doesn't hold a mutable state.
>>
>> if so, how do i implement something that HAS to hold a state? what if let's say 10 clients try to add elements to the same list instance? there has to be a managing class that holds the list, right?
>>
>>
>> --
>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
>
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

HamsterofDeath
In reply to this post by Razvan Cojocaru-2
i can imagine programming everything using only immutable objects/structs/values as long as there is one *mutable* entry point for the current complete world which i then navigate through.

for example, in tetris, there's a board. i can easily do:
val newBoard = oldBoard.withUserMove(move)
to execute a single move and get the resulting board.

but to make the game run forever, i need at least ONE global mutable state do be able to do this:

var myMostRecentWorld = new Board
while (true) {
   myMostRecentWorld = myMostRecentWorld.withUserMove(getMoveFromSomeWhere)
}

if i try to avoid even that mutable state, i can only come up with *really* weird stuff like

def advanceOneStep(world:Board) {
   advanceOneStep(world.withUserMove(getMoveFromSomeWhere)
}
 
which will eventually lead to a stackoverflow or outofmemory

how does the state/io-monad work? like my "var currentWorld"?


-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 07:27:34 -0500
> Von: Razvan Cojocaru <[hidden email]>
> An: Dennis Haupt <[hidden email]>
> CC: Robert Wills <[hidden email]>, "[hidden email]" <[hidden email]>
> Betreff: Re: [scala-user] functional/immutable programming question

> It's like the IO monad but a little different ;)
>
> Thanks,
> Razvan
>
> On 2010-11-11, at 5:00 AM, "Dennis Haupt" <[hidden email]> wrote:
>
> > what is a state monad?
> >
> > -------- Original-Nachricht --------
> >> Datum: Thu, 11 Nov 2010 09:53:56 +0000
> >> Von: Robert Wills <[hidden email]>
> >> An: Dennis Haupt <[hidden email]>
> >> CC: [hidden email]
> >> Betreff: Re: [scala-user] functional/immutable programming question
> >
> >> In a pure language the 'something' holding the state would be a state
> >> or writer monad.
> >>
> >> Of course if this were a proper client-server environment you would
> >> need to have some impurity or else your program would never be able to
> >> handle non-determinism.
> >>
> >> -Rob
> >>
> >> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> >>> in pure functional programming, there are no side effects. this means,
> >> the only "effect" a method has is its returned value, right? it doesn't
> hold
> >> a mutable state.
> >>>
> >>> if so, how do i implement something that HAS to hold a state? what if
> >> let's say 10 clients try to add elements to the same list instance?
> there has
> >> to be a managing class that holds the list, right?
> >>>
> >>>
> >>> --
> >>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> >>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
> >>>
> >
> > --
> > GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl

--
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!  
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Andreas Flierl
In reply to this post by Robert Wills-2

Robert Wills <[hidden email]> wrote:
> sciss is right.  Pure fp doesn't solve all your problems and there is
> inevitably going to be some point of your program which is impure.
> Things like the State monad help ensure that that purity is isolated
> in one part of your program.  Haskell programs generally keep all the
> 'dynamic' or non-deterministic stuff in one part of the program by
> using a stack of monads and other pointy-headed stuff.  Arguably, this
> can make them hard to understand but it does make them very safe and
> very easily testable.

I think either you or me are confusing concepts here, so please bear
with me:

In my understanding, IO monad and the like are exactly for keeping
impurity out of your program. That's exactly why Haskell uses monads for
IO etc. So as long as you use monads for the dynamic parts, you're still
pure. The way to introduce impurity in Haskell would be "unsafe"
functions (unsafeIO etc.) which again can only be called from unsafe
functions (?). Am I missing something?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Andreas Flierl
In reply to this post by HamsterofDeath

Am Donnerstag, den 11.11.2010, 14:04 +0100 schrieb "Dennis Haupt"
<[hidden email]>:
> i can imagine programming everything using only immutable
> objects/structs/values as long as there is one *mutable* entry point
> for the current complete world which i then navigate through.

I found James Iry's blog a good read for that topic:
http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html

(this part introduces the IO monad, the basics are in part 1-3, linked
from the above page)

Kind regards
Andreas
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Razvan Cojocaru-2
In reply to this post by HamsterofDeath
The first approximation for a state monad is an entity that wraps a state.
You can only change the state that's inside the monad, by passing the monad
a function that changes the state and then let the monad invoke your
function and change the state accordingly.

If you think of it that way, the state itself is never visible outside the
monad (or it doesn't have to be). That's how you guarantee that nobody can
mess with it outside of the monad's control.

A monad is really an extension to something like this:

atomically (f,g) = {  // simplified STM monad
   lockandstarttransaction
   var v = readoldvalue
    v = f (v)
    v = g (v)
    setnewvalue (v)
    unlockandendtransaction
}

As you see, the actual value never escapes the "monad"...

The mathematics behind it, the scala syntax (for comprehension) and the
actual function signatures are a little more complicated, to allow
composition, but this is the general idea...

scalaz has a state monad, here's a good post on that:
http://blog.tmorris.net/the-state-monad-for-scala-users/

here's an (complex) example of using the scalaz.State monad:
https://github.com/scalaz/scalaz/blob/master/example/src/main/scala/scalaz/example/ExampleState.scala

good luck!
Razvan


-----Original Message-----
From: Dennis Haupt
Sent: Thursday, November 11, 2010 8:04 AM
To: Razvan Cojocaru
Cc: [hidden email] ; [hidden email]
Subject: Re: [scala-user] functional/immutable programming question

i can imagine programming everything using only immutable
objects/structs/values as long as there is one *mutable* entry point for the
current complete world which i then navigate through.

for example, in tetris, there's a board. i can easily do:
val newBoard = oldBoard.withUserMove(move)
to execute a single move and get the resulting board.

but to make the game run forever, i need at least ONE global mutable state
do be able to do this:

var myMostRecentWorld = new Board
while (true) {
   myMostRecentWorld = myMostRecentWorld.withUserMove(getMoveFromSomeWhere)
}

if i try to avoid even that mutable state, i can only come up with *really*
weird stuff like

def advanceOneStep(world:Board) {
   advanceOneStep(world.withUserMove(getMoveFromSomeWhere)
}

which will eventually lead to a stackoverflow or outofmemory

how does the state/io-monad work? like my "var currentWorld"?


-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 07:27:34 -0500
> Von: Razvan Cojocaru <[hidden email]>
> An: Dennis Haupt <[hidden email]>
> CC: Robert Wills <[hidden email]>, "[hidden email]"
> <[hidden email]>
> Betreff: Re: [scala-user] functional/immutable programming question

> It's like the IO monad but a little different ;)
>
> Thanks,
> Razvan
>
> On 2010-11-11, at 5:00 AM, "Dennis Haupt" <[hidden email]> wrote:
>
> > what is a state monad?
> >
> > -------- Original-Nachricht --------
> >> Datum: Thu, 11 Nov 2010 09:53:56 +0000
> >> Von: Robert Wills <[hidden email]>
> >> An: Dennis Haupt <[hidden email]>
> >> CC: [hidden email]
> >> Betreff: Re: [scala-user] functional/immutable programming question
> >
> >> In a pure language the 'something' holding the state would be a state
> >> or writer monad.
> >>
> >> Of course if this were a proper client-server environment you would
> >> need to have some impurity or else your program would never be able to
> >> handle non-determinism.
> >>
> >> -Rob
> >>
> >> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> >>> in pure functional programming, there are no side effects. this means,
> >> the only "effect" a method has is its returned value, right? it doesn't
> hold
> >> a mutable state.
> >>>
> >>> if so, how do i implement something that HAS to hold a state? what if
> >> let's say 10 clients try to add elements to the same list instance?
> there has
> >> to be a managing class that holds the list, right?
> >>>
> >>>
> >>> --
> >>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> >>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
> >>>
> >
> > --
> > GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl

--
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail 

Razvan Cojocaru,
Work: http://www.sigma-systems.com
Playground: http://wiki.homecloud.ca
Latest cool toys: Scripster and Gremlins
Follow me: RSS Feed, Twitter, GitHub.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Razvan Cojocaru-2
In reply to this post by HamsterofDeath
The first approximation for a state monad is an entity that wraps a state.
You can only change the state that's inside the monad, by passing the monad
a function that changes the state and then let the monad invoke your
function and change the state accordingly.

If you think of it that way, the state itself is never visible outside the
monad (or it doesn't have to be). That's how you guarantee that nobody can
mess with it outside of the monad's control.

A monad is really an extension to something like this:

atomically (f,g) = {  // simplified STM monad
   lockandstarttransaction
   var v = readoldvalue
    v = f (v)
    v = g (v)
    setnewvalue (v)
    unlockandendtransaction
}

As you see, the actual value never escapes the "monad"...

The mathematics behind it, the scala syntax (for comprehension) and the
actual function signatures are a little more complicated, to allow
composition, but this is the general idea...

scalaz has a state monad, here's a good post on that:
http://blog.tmorris.net/the-state-monad-for-scala-users/

here's an (complex) example of using the scalaz.State monad:
https://github.com/scalaz/scalaz/blob/master/example/src/main/scala/scalaz/example/ExampleState.scala

good luck!
Razvan


-----Original Message-----
From: Dennis Haupt
Sent: Thursday, November 11, 2010 8:04 AM
To: Razvan Cojocaru
Cc: [hidden email] ; [hidden email]
Subject: Re: [scala-user] functional/immutable programming question

i can imagine programming everything using only immutable
objects/structs/values as long as there is one *mutable* entry point for the
current complete world which i then navigate through.

for example, in tetris, there's a board. i can easily do:
val newBoard = oldBoard.withUserMove(move)
to execute a single move and get the resulting board.

but to make the game run forever, i need at least ONE global mutable state
do be able to do this:

var myMostRecentWorld = new Board
while (true) {
   myMostRecentWorld = myMostRecentWorld.withUserMove(getMoveFromSomeWhere)
}

if i try to avoid even that mutable state, i can only come up with *really*
weird stuff like

def advanceOneStep(world:Board) {
   advanceOneStep(world.withUserMove(getMoveFromSomeWhere)
}

which will eventually lead to a stackoverflow or outofmemory

how does the state/io-monad work? like my "var currentWorld"?


-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 07:27:34 -0500
> Von: Razvan Cojocaru <[hidden email]>
> An: Dennis Haupt <[hidden email]>
> CC: Robert Wills <[hidden email]>, "[hidden email]"
> <[hidden email]>
> Betreff: Re: [scala-user] functional/immutable programming question

> It's like the IO monad but a little different ;)
>
> Thanks,
> Razvan
>
> On 2010-11-11, at 5:00 AM, "Dennis Haupt" <[hidden email]> wrote:
>
> > what is a state monad?
> >
> > -------- Original-Nachricht --------
> >> Datum: Thu, 11 Nov 2010 09:53:56 +0000
> >> Von: Robert Wills <[hidden email]>
> >> An: Dennis Haupt <[hidden email]>
> >> CC: [hidden email]
> >> Betreff: Re: [scala-user] functional/immutable programming question
> >
> >> In a pure language the 'something' holding the state would be a state
> >> or writer monad.
> >>
> >> Of course if this were a proper client-server environment you would
> >> need to have some impurity or else your program would never be able to
> >> handle non-determinism.
> >>
> >> -Rob
> >>
> >> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> >>> in pure functional programming, there are no side effects. this means,
> >> the only "effect" a method has is its returned value, right? it doesn't
> hold
> >> a mutable state.
> >>>
> >>> if so, how do i implement something that HAS to hold a state? what if
> >> let's say 10 clients try to add elements to the same list instance?
> there has
> >> to be a managing class that holds the list, right?
> >>>
> >>>
> >>> --
> >>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> >>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
> >>>
> >
> > --
> > GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl

--
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail 

Razvan Cojocaru,
Work: http://www.sigma-systems.com
Playground: http://wiki.homecloud.ca
Latest cool toys: Scripster and Gremlins
Follow me: RSS Feed, Twitter, GitHub.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

HamsterofDeath
In reply to this post by Razvan Cojocaru-2
yay, something to read :D

-------- Original-Nachricht --------
> Datum: Thu, 11 Nov 2010 08:55:48 -0500
> Von: "Razvan Cojocaru" <[hidden email]>
> An: "Dennis Haupt" <[hidden email]>
> CC: [hidden email], [hidden email]
> Betreff: Re: [scala-user] functional/immutable programming question

> The first approximation for a state monad is an entity that wraps a state.
> You can only change the state that's inside the monad, by passing the
> monad
> a function that changes the state and then let the monad invoke your
> function and change the state accordingly.
>
> If you think of it that way, the state itself is never visible outside the
> monad (or it doesn't have to be). That's how you guarantee that nobody can
> mess with it outside of the monad's control.
>
> A monad is really an extension to something like this:
>
> atomically (f,g) = {  // simplified STM monad
>    lockandstarttransaction
>    var v = readoldvalue
>     v = f (v)
>     v = g (v)
>     setnewvalue (v)
>     unlockandendtransaction
> }
>
> As you see, the actual value never escapes the "monad"...
>
> The mathematics behind it, the scala syntax (for comprehension) and the
> actual function signatures are a little more complicated, to allow
> composition, but this is the general idea...
>
> scalaz has a state monad, here's a good post on that:
> http://blog.tmorris.net/the-state-monad-for-scala-users/
>
> here's an (complex) example of using the scalaz.State monad:
> https://github.com/scalaz/scalaz/blob/master/example/src/main/scala/scalaz/example/ExampleState.scala
>
> good luck!
> Razvan
>
>
> -----Original Message-----
> From: Dennis Haupt
> Sent: Thursday, November 11, 2010 8:04 AM
> To: Razvan Cojocaru
> Cc: [hidden email] ; [hidden email]
> Subject: Re: [scala-user] functional/immutable programming question
>
> i can imagine programming everything using only immutable
> objects/structs/values as long as there is one *mutable* entry point for
> the
> current complete world which i then navigate through.
>
> for example, in tetris, there's a board. i can easily do:
> val newBoard = oldBoard.withUserMove(move)
> to execute a single move and get the resulting board.
>
> but to make the game run forever, i need at least ONE global mutable state
> do be able to do this:
>
> var myMostRecentWorld = new Board
> while (true) {
>    myMostRecentWorld =
> myMostRecentWorld.withUserMove(getMoveFromSomeWhere)
> }
>
> if i try to avoid even that mutable state, i can only come up with
> *really*
> weird stuff like
>
> def advanceOneStep(world:Board) {
>    advanceOneStep(world.withUserMove(getMoveFromSomeWhere)
> }
>
> which will eventually lead to a stackoverflow or outofmemory
>
> how does the state/io-monad work? like my "var currentWorld"?
>
>
> -------- Original-Nachricht --------
> > Datum: Thu, 11 Nov 2010 07:27:34 -0500
> > Von: Razvan Cojocaru <[hidden email]>
> > An: Dennis Haupt <[hidden email]>
> > CC: Robert Wills <[hidden email]>, "[hidden email]"
> > <[hidden email]>
> > Betreff: Re: [scala-user] functional/immutable programming question
>
> > It's like the IO monad but a little different ;)
> >
> > Thanks,
> > Razvan
> >
> > On 2010-11-11, at 5:00 AM, "Dennis Haupt" <[hidden email]> wrote:
> >
> > > what is a state monad?
> > >
> > > -------- Original-Nachricht --------
> > >> Datum: Thu, 11 Nov 2010 09:53:56 +0000
> > >> Von: Robert Wills <[hidden email]>
> > >> An: Dennis Haupt <[hidden email]>
> > >> CC: [hidden email]
> > >> Betreff: Re: [scala-user] functional/immutable programming question
> > >
> > >> In a pure language the 'something' holding the state would be a state
> > >> or writer monad.
> > >>
> > >> Of course if this were a proper client-server environment you would
> > >> need to have some impurity or else your program would never be able
> to
> > >> handle non-determinism.
> > >>
> > >> -Rob
> > >>
> > >> On Thu, Nov 11, 2010 at 9:45 AM, Dennis Haupt <[hidden email]> wrote:
> > >>> in pure functional programming, there are no side effects. this
> means,
> > >> the only "effect" a method has is its returned value, right? it
> doesn't
> > hold
> > >> a mutable state.
> > >>>
> > >>> if so, how do i implement something that HAS to hold a state? what
> if
> > >> let's say 10 clients try to add elements to the same list instance?
> > there has
> > >> to be a managing class that holds the list, right?
> > >>>
> > >>>
> > >>> --
> > >>> GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > >>> gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
> > >>>
> > >
> > > --
> > > GMX DSL Doppel-Flat ab 19,99 &euro;/mtl.! Jetzt auch mit
> > > gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl
>
> --
> Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!
> Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail 
>

--
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!  
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: functional/immutable programming question

Det2
In reply to this post by HamsterofDeath
> if i try to avoid even that mutable state, i can only come up with
> *really* weird stuff like
>
> def advanceOneStep(world:Board) {
>    advanceOneStep(world.withUserMove(getMoveFromSomeWhere)
> }
>
> which will eventually lead to a stackoverflow or outofmemory


Why?

I mean, when talking about pure functional things, you are also
talking about tail recursion, and the solution above seems to
be one in my eyes.
With tail-call-optimization there shouldn't be any memory problems
so far for this simple example.



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Tony Morris
In reply to this post by Sc iss
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/11/10 22:30, Sciss wrote:

> fp and immutable data structures are celebrated as solving all
> problems, but as you see, they don't, in particular they have no
> clear concept of dynamicity, so things that change over time. they
> don't solve your problem of concurrent access here, so you will
> need to linearize your clients in some way. for example, you could
> manage them with an Actor or use an STM... immutable structures and
> STM play nicely together, as when a transaction is aborted you
> haven't crippled your data structure, just the newly created copy
> (old list plus new head element, for instance) isn't stored in the
> ref, no damage is done.
>
> best, -sciss-
Beware, nonsense lurks there.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzcUkAACgkQmnpgrYe6r616mwCgr4kl31vSxo36XwH70Jt71d1z
9tcAnii11F1SLyI/XOiFNLNUOUelyzZu
=3FTH
-----END PGP SIGNATURE-----

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Tony Morris
In reply to this post by HamsterofDeath
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/11/10 20:00, Dennis Haupt wrote:
> what is a state monad?
>
Given:  case class State[S, A](f: S => (S, A))

object StateMonad {
    def bind[A, B](s: State[S, A], f: A => State[S, B]): State[S, B] =
error("todo")

    def pure[S, A](a: => A): State[S, A] = error("todo")
}

The monad is the implementation of the two functions above satisfying
left/right identity for pure and associativity for bind.

PS: I'd like to also point out that this discussion has absolutely
nothing to do with monads and existence otherwise is a (common)
symptom of failing to identify essentials. Expect a lot of mythology
floating passed your inbox.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzcU4AACgkQmnpgrYe6r62+3QCbBomI9BC9bynIAOioq7q3yNoR
d4sAninbiklAjj1+YLpwaYTtVFZf7Cpk
=ALqJ
-----END PGP SIGNATURE-----

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Tony Morris
In reply to this post by HamsterofDeath
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/11/10 00:14, Dennis Haupt wrote:
> yay, something to read :D

Let me know if you have questions. (I wrote the mentioned scalaz data
structure and the blog post).


- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzcVAEACgkQmnpgrYe6r62PbgCgoscFe0TyjqQMLQLyvb+7XGRY
RbcAoMEuboSVXk5S2pGILGK1svPXWl/E
=1pyK
-----END PGP SIGNATURE-----

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Tony Morris
In reply to this post by Andreas Flierl
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/11/10 23:12, Andreas Flierl wrote:
>
> Robert Wills [hidden email] wrote:
>> sciss is right.  Pure fp doesn't solve all your problems and
>> there is inevitably going to be some point of your program which
>> is impure. Things like the State monad help ensure that that
>> purity is isolated in one part of your program.  Haskell
>> programs generally keep all the 'dynamic' or non-deterministic
>> stuff in one part of the program by using a stack of monads and
>> other pointy-headed stuff.  Arguably, this can make them hard to
>> understand but it does make them very safe and very easily
>> testable.
>
> I think either you or me are confusing concepts here, so please
> bear with me:
>
> In my understanding, IO monad and the like are exactly for keeping
>  impurity out of your program. That's exactly why Haskell uses
> monads for IO etc. So as long as you use monads for the dynamic
> parts, you're still pure. The way to introduce impurity in Haskell
> would be "unsafe" functions (unsafeIO etc.) which again can only
> be called from unsafe functions (?). Am I missing something?

No you are not missing anything. You are completely correct with one
minor caveat.

In this discussion, we are not referring to the IO
monad (except when we misidentify) but the IO type constructor.

I strongly advise against using the irrelevant term "monad" for this
purpose. Here's why.

IO is also:
* an applicative functor
* a pointed functor
* a covariant functor
* a monoid
* many other things

Notice we are not saying "the IO applicative functor." That's because
it is irrelevant -- just as irrelevant as using the term monad. The
term monad gets much more attention than it deserves. This attention
has a *detrimental effect* on people trying to learn, because they
too, will wonder about the relevance as they try to form a concept.

In this discussion, we are talking about the IO type constructor or
perhaps IO values, but I've not seen any valid reference to the IO
monad or the IO functor or any other thing that continues to be
irrelevant.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzcVV0ACgkQmnpgrYe6r60LhACghL+ZGFy+WRoB+yrcyIKFImmn
FcIAoJym6a1ZzZmyLlpttFR21qIqQGA+
=2bxm
-----END PGP SIGNATURE-----

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: functional/immutable programming question

Sc iss
In reply to this post by Tony Morris
beware, your comments are a waste of time. if you want to help in this thread, break down your superior knowledge in a way that it is shared with others, and explain why something is nonsense in your opinion.

Am 11.11.2010 um 20:29 schrieb Tony Morris:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 11/11/10 22:30, Sciss wrote:
>> fp and immutable data structures are celebrated as solving all
>> problems, but as you see, they don't, in particular they have no
>> clear concept of dynamicity, so things that change over time. they
>> don't solve your problem of concurrent access here, so you will
>> need to linearize your clients in some way. for example, you could
>> manage them with an Actor or use an STM... immutable structures and
>> STM play nicely together, as when a transaction is aborted you
>> haven't crippled your data structure, just the newly created copy
>> (old list plus new head element, for instance) isn't stored in the
>> ref, no damage is done.
>>
>> best, -sciss-
> Beware, nonsense lurks there.
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAkzcUkAACgkQmnpgrYe6r616mwCgr4kl31vSxo36XwH70Jt71d1z
> 9tcAnii11F1SLyI/XOiFNLNUOUelyzZu
> =3FTH
> -----END PGP SIGNATURE-----
>

1234 ... 7
Loading...