Re: [Haskell-cafe] Re: A bit of a shock - Memoizing functions

[Kirk Martinez]

It seems there is a very close correspondence between data structures and
functions in Haskell.  Your powersOfTwo function, since it gets memoized
automatically (is this the case for all functions of zero arguments?), seems
exactly like a data structure.  This harks back to my Scheme days when we
learned about the close relationship between code and data.

I wonder: does the converse exist?  Haskell data constructors which are
really functions?  How and for what might one use those?

Thanks,
Kirk

On Fri, Mar 27, 2009 at 1:58 PM, GüŸnther Schmidt wrote:

> Hi Bulat,
>
> that is so cool!
>
> Günther
>
> Bulat Ziganshin schrieb:
>
>> Hello Gü?nther,
>>
>> Friday, March 27, 2009, 11:30:41 PM, you wrote:
>>
>>  Some of the memoizing functions, they actually "remember" stuff
>>> *between* calls?
>>>
>>
>> what i've seen in haskell - functions relying on lazy datastructures
>> that ensure computation on first usage so this looks exactly like as
>> memoizing:
>>
>> power 2 n | n>=0 && n<100 = powersOfTwo!n
>> power x y = x^y
>>
>> powersOfTwo = array (0,99) [2^n | n <- [0..99] ]
>>
>>
>> it's almost exact definition from ghc Prelude
>>
>>
>>
>>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: A bit of a shock - Memoizing functions

[Jonathan Cast]

On Fri, 2009-03-27 at 14:26 -0700, Kirk Martinez wrote:
> Your powersOfTwo function, since it gets memoized automatically (is
> this the case for all functions of zero arguments?),

It is the case for all functions which have zero arguments *at the time
they are presented to the code generator*.  The infamous evil
monomorphism restriction arises from the fact that overloaded
expressions, such as

negative_one = exp(pi * sqrt(-1))

look like functions of zero arguments, but are not, and hence do not get
memoized.  This behavior was considered sufficiently surprising, when it
was discovered in early Haskell compilers, that the construct was
outlawed from the language entirely.

jcc


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

Re: [Haskell-cafe] Re: A bit of a shock - Memoizing functions

[David Menendez]

2009/3/27 Kirk Martinez :
> It seems there is a very close correspondence between data structures and
> functions in Haskell.  Your powersOfTwo function, since it gets memoized
> automatically (is this the case for all functions of zero arguments?), seems
> exactly like a data structure.

That's because it is. It's an array whose elements are computed on demand.

>  This harks back to my Scheme days when we
> learned about the close relationship between code and data.
>
> I wonder: does the converse exist?  Haskell data constructors which are
> really functions?  How and for what might one use those?

Sure. You can use Church encoding to represent any Haskell data type
as a function.

-- 
Dave Menendez 

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

Re: [Haskell-cafe] Re: A bit of a shock - Memoizing functions

[Dan Piponi]

2009/3/27 Kirk Martinez :

> I wonder: does the converse exist?  Haskell data constructors which are
> really functions?  How and for what might one use those?

You might enjoy reading about the use of tries for memoisation. Conal
Elliott explains nicely how you can an isomorphism between certain
types of function and certain types of tree structure:
http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

It's neat because the rules for constructing the isomorphism are just
like some well known rules of high school algebra, but interpreted in
a new way.
--
Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: A bit of a shock - Memoizing functions

[Martijn van Steenbergen]

Kirk Martinez wrote:
It seems there is a very close correspondence between data structures 
and functions in Haskell.  Your powersOfTwo function, since it gets 
memoized automatically (is this the case for all functions of zero 
arguments?), seems exactly like a data structure.  This harks back to my 
Scheme days when we learned about the close relationship between code 
and data.


You might also find Neil's blog post about CAFs interesting:

http://neilmitchell.blogspot.com/2009/02/monomorphism-and-defaulting.html

Fijne avond,

Martijn.

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