Non-recursive binding expression

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

Non-recursive binding expression

José Romildo Malaquias
Hello.

Is there any non-recursive binding expression in Haskell?

Something that would allow me to write, for instance,

  test = let' xs = [] in
         let' xs = 3 : xs in
         let' xs = 8 : xs in
         let' xs = 7 : xs in
         xs

Here let' is an hypothetical construction similar to let, except that it
would be non-recursive. In the example, the value of test would be
[7,8,3].

So, is there something in this line in Haskell?

Regards,

Jos? Romildo
Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Will Ness-2
 <j.romildo <at> gmail.com> writes:

>
> Hello.
>
> Is there any non-recursive binding expression in Haskell?
>
> Something that would allow me to write, for instance,
>
>   test = let' xs = [] in
>          let' xs = 3 : xs in
>          let' xs = 8 : xs in
>          let' xs = 7 : xs in
>          xs
>
> Here let' is an hypothetical construction similar to let, except that it
> would be non-recursive. In the example, the value of test would be
> [7,8,3].
>
> So, is there something in this line in Haskell?
>
> Regards,
>
> Jos? Romildo
>


Well, it's not a nice thing to do (probably), but you can write

test = head $
  do xs <- [ [] ]
     xs <- [ 3:xs ]
     xs <- [ 8:xs ]
     xs <- [ 7:xs ]
     return xs



Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Brent Yorgey-2
On Sat, Feb 28, 2009 at 05:19:03PM +0000, Will Ness wrote:

>  <j.romildo <at> gmail.com> writes:
>
> >
> > Hello.
> >
> > Is there any non-recursive binding expression in Haskell?
> >
> > Something that would allow me to write, for instance,
> >
> >   test = let' xs = [] in
> >          let' xs = 3 : xs in
> >          let' xs = 8 : xs in
> >          let' xs = 7 : xs in
> >          xs
>
> Well, it's not a nice thing to do (probably), but you can write
>
> test = head $
>   do xs <- [ [] ]
>      xs <- [ 3:xs ]
>      xs <- [ 8:xs ]
>      xs <- [ 7:xs ]
>      return xs
>

The correct answer is no.  Life is pain.  Anyone who says otherwise is
selling something. ;)

Assignment in Haskell is not destructive update---it assigns a name to
a value, and they become one flesh, until parted by death (i.e. the
end of their lexical scope).  The only reason Will's code works is
that each line creates a new lexical scope, and each xs shadows the
previous one.

To do what you want, you have to give each thing a new name, something
like this:

test = let xs = []
           xs' = 3 : xs
           xs'' = 8 : xs'
           xs''' = 7 : xs''
       in xs'''

"But this is horribly painful!" you cry.  Of course it is!  Giving
names to things you don't want to keep is always painful (like when
your child names the almost-dead raccoon you find in the street, which
is just going to die or be given to an animal shelter anyway).

So, why not just avoid naming things you don't want?

test = (7:) . (8:) . (3:) $ []

Ah, that's better!  We just thread some intermediate values through a
chain of composed functions.  Each function does its little bit of
modification and passes the intermediate value along to the next
function, and the intermediate values are never given names.

-Brent
Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Will Ness-2
Brent Yorgey <byorgey <at> seas.upenn.edu> writes:

>
> On Sat, Feb 28, 2009 at 05:19:03PM +0000, Will Ness wrote:
> >  <j.romildo <at> gmail.com> writes:
> >
> > >
> > > Hello.
> > >
> > > Is there any non-recursive binding expression in Haskell?
> > >
> > > Something that would allow me to write, for instance,
> > >
> > >   test = let' xs = [] in
> > >          let' xs = 3 : xs in
> > >          let' xs = 8 : xs in
> > >          let' xs = 7 : xs in
> > >          xs
> >
> > Well, it's not a nice thing to do (probably), but you can write
> >
> > test = head $
> >   do xs <- [ [] ]
> >      xs <- [ 3:xs ]
> >      xs <- [ 8:xs ]
> >      xs <- [ 7:xs ]
> >      return xs
> >
>
> The correct answer is no.  Life is pain.  Anyone who says otherwise is
> selling something. ;)
>
> Assignment in Haskell is not destructive update---it assigns a name to
> a value, and they become one flesh, until parted by death (i.e. the
> end of their lexical scope).  The only reason Will's code works is
> that each line creates a new lexical scope, and each xs shadows the
> previous one.


That's what I understood the OP wanted - Scheme's LET, not LETREC, allowing for
shadowing. I was suprised let-statement in do chain didn't work that way. I
expected it to be equivalent to a kind of code above, since each new line in do
block represents a nested function in explicit bind notation, and nested
function binding definitely provides for non-recursive let kind of argument
binding, with shadowing.

I thought the whole point of having special let statement in do notation was
not to have to write the kind of code above with singleton lists. Since we have
shadowing there, it should've been so in let-statements too. Isn't it?


>
> To do what you want, you have to give each thing a new name, something
> like this:
>
> test = let xs = []
>            xs' = 3 : xs
>   xs'' = 8 : xs'
>   xs''' = 7 : xs''
>        in xs'''
>
> "But this is horribly painful!" you cry.  Of course it is!  Giving
> names to things you don't want to keep is always painful (like when
> your child names the almost-dead raccoon you find in the street, which
> is just going to die or be given to an animal shelter anyway).
>
> So, why not just avoid naming things you don't want?
>
> test = (7:) . (8:) . (3:) $ []
>
> Ah, that's better!  We just thread some intermediate values through a
> chain of composed functions.  Each function does its little bit of
> modification and passes the intermediate value along to the next
> function, and the intermediate values are never given names.
>
> -Brent
>


BTW could there be a use for something like

 infixl 1 #

 x # f = f x    -- (#) = flip ($)

to have the direct data flow reflected in our code, so that your code would
become

 test = [] # (3:) # (8:) # (7:)

maybe sometimes it's more natural to think of data being "piped through" the
chain of functions, and to write them down in forward, not reverse order of
application?



Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Ertugrul Söylemez
Will Ness <[hidden email]> wrote:

> BTW could there be a use for something like
>
>  infixl 1 #
>
>  x # f = f x    -- (#) = flip ($)
>
> to have the direct data flow reflected in our code, so that your code
> would become
>
>  test = [] # (3:) # (8:) # (7:)
>
> maybe sometimes it's more natural to think of data being "piped
> through" the chain of functions, and to write them down in forward,
> not reverse order of application?

I think, it's more natural to think in terms of functions, and often the
argument to a function is not just something as simple as [] anyway.  If
you want to think in chaining instead of composition, you can use arrow
sequencing (>>>) instead of function composition (.):

  import Control.Arrow

  test = (3:) >>> (8:) >>> (7:) $ []


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/


Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Brent Yorgey-2
In reply to this post by Will Ness-2
On Sat, Feb 28, 2009 at 10:31:37PM +0000, Will Ness wrote:

>
> That's what I understood the OP wanted - Scheme's LET, not LETREC, allowing for
> shadowing. I was suprised let-statement in do chain didn't work that way. I
> expected it to be equivalent to a kind of code above, since each new line in do
> block represents a nested function in explicit bind notation, and nested
> function binding definitely provides for non-recursive let kind of argument
> binding, with shadowing.
>
> I thought the whole point of having special let statement in do notation was
> not to have to write the kind of code above with singleton lists. Since we have
> shadowing there, it should've been so in let-statements too. Isn't it?

No, the point of let expressions in do-blocks is to have a convenient
way to make pure bindings, i.e. ones that aren't piped through >>= .
Note that let statements in do-blocks just get desugared into normal
let expressions:

  do { let x = y ; stuff }
 
    desugars into

  let x = y in do { stuff }

Haskell simply doesn't have anything equivalent to Scheme's LET,
except for actual nested functions.

-Brent
Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

José Romildo Malaquias
In reply to this post by Brent Yorgey-2
On Sat, Feb 28, 2009 at 01:01:56PM -0500, Brent Yorgey wrote:

> On Sat, Feb 28, 2009 at 05:19:03PM +0000, Will Ness wrote:
> >  <j.romildo <at> gmail.com> writes:
> >
> > >
> > > Hello.
> > >
> > > Is there any non-recursive binding expression in Haskell?
> > >
> > > Something that would allow me to write, for instance,
> > >
> > >   test = let' xs = [] in
> > >          let' xs = 3 : xs in
> > >          let' xs = 8 : xs in
> > >          let' xs = 7 : xs in
> > >          xs
> >
> > Well, it's not a nice thing to do (probably), but you can write
> >
> > test = head $
> >   do xs <- [ [] ]
> >      xs <- [ 3:xs ]
> >      xs <- [ 8:xs ]
> >      xs <- [ 7:xs ]
> >      return xs
> >
>
> The correct answer is no.  Life is pain.  Anyone who says otherwise is
> selling something. ;)
>
> Assignment in Haskell is not destructive update---it assigns a name to
> a value, and they become one flesh, until parted by death (i.e. the
> end of their lexical scope).  The only reason Will's code works is
> that each line creates a new lexical scope, and each xs shadows the
> previous one.

I am not asking for assignment. What I want is indeed what I already
said: a new lexical scope which introduces a new variable, but the
variable name is being reused. That shadows the previous definition.

What I want is the possibilitiy of a non-recursive binding expression,
like my hypothecial let' construction. Being non-recursive,

   let' <var> = <exp1> in <exp2>

any occurrence of <var> in <exp1> does not refer to the new varibale
being introduced, but to some previous defined variable named <var>. If
that does exist, than there is a semantic error in the expression
(unless <var> is not used in <exp1>, of course). So the scope of <var>
is just <exp2>. It does not include <exp1>. If it was a recursive
definition, the scope of <var> would be <exp1> *and* <exp2>.

Romildo
Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Will Ness-2
 <j.romildo <at> gmail.com> writes:

>
> On Sat, Feb 28, 2009 at 01:01:56PM -0500, Brent Yorgey wrote:
> > On Sat, Feb 28, 2009 at 05:19:03PM +0000, Will Ness wrote:
> > >  <j.romildo <at> gmail.com> writes:
> > >
> > > > Is there any non-recursive binding expression in Haskell?
> > >
> > Assignment in Haskell is not destructive update.
>
> I am not asking for assignment. What I want is indeed what I already
> said: a new lexical scope which introduces a new variable, but the
> variable name is being reused. That shadows the previous definition.
>
> Romildo


The code I posted has exactly these semantics:

When we write

  test = head $
    do xs <- [ [] ]
       xs <- [ 3:xs ]
       xs <- [ 8:xs ]
       xs <- [ 7:xs ]
       return xs

each xs in a singleton generator refers to its previous binding.


Reply | Threaded
Open this post in threaded view
|

Re: Non-recursive binding expression

Will Ness-2
In reply to this post by Brent Yorgey-2
Brent Yorgey <byorgey <at> seas.upenn.edu> writes:

>
> On Sat, Feb 28, 2009 at 10:31:37PM +0000, Will Ness wrote:
> >
> > That's what I understood the OP wanted - Scheme's LET, not LETREC, allowing
for
> > shadowing. I was suprised let-statement in do chain didn't work that way. I
> > expected it to be equivalent to a kind of code above, since each new line
in do

> > block represents a nested function in explicit bind notation, and nested
> > function binding definitely provides for non-recursive let kind of argument
> > binding, with shadowing.
> >
>
> No, the point of let expressions in do-blocks is to have a convenient
> way to make pure bindings, i.e. ones that aren't piped through >>= .
> Note that let statements in do-blocks just get desugared into normal
> let expressions:
>
>   do { let x = y ; stuff }
>
>     desugars into
>
>   let x = y in do { stuff }
>
> Haskell simply doesn't have anything equivalent to Scheme's LET,
> except for actual nested functions.
>
> -Brent
>


Shadowing has its legitimate uses, for example when some value is refined while
being propagated through a chain of action-functions, there is no reason for
action-functions further down in the chain to have access to its previous,
outdated version.

Consider generating (i,j,k) triples representing Hamming numbers in some range,
along with their logarithm value, q = i*log 2 + j*log 3 + k*log 5, which gets
partially built as new indices get generated:

  do k <- [0..kmax]
     q <- [ k*log 5 ]
     j <- [0..jmax]
     q <- [ q + j*log 3]
     i <- [0..imax]
     q <- [ q + i*log 2]
     return ((i,j,k),q)

Why not have some syntactic adornement in place of ugly-looking singleton
generators? Calling it LET got it confused with the regular LET; calling it SET
doesn't have to confuse anyone to believe it's destructive (it's not).

But if it's a syntactic re-write it ought to follow the semantics of the
original construct.

The possibility of having shadowing definitions got eliminated here with this
LET rewrite. It's not right.

After all, if we really had to have some recursive definition, we could always
use the regular let expression, like

  do a <- as
     set q = let zs=0:zs in zs
     b <- bs
     ....

could we?


Cheers,