pointfree notation

Thanks for the article(s), I am looking at pointfree notation, which I
had previously understood to be basically just eta-reduction, but now
wonder about that conclusion.

For example your example,
numOccurrences x = length . filter (== x)
seems fine, but
numOccurrences = (length .) . filter . (==)
worries me.

Seems to me that it wouldn't typecheck. I don't use Haskell (rather
SML), but also assume that all of your functions are curried.
basically it seem that the intention is that == should consume only
one argument, and leave its result and the other for filter; i.e. the
list argument is not consumed by the first function in the pipeline
(==), but left for the 2nd (filter)

How would a compiler (interpreter) know about that argument
parcelling, v.s. a strict linear pipeline of arguments?

length :: a-list -> int
filter :: a-list -> ( a -> bool) -> a-list
==  ::  int -> int -> bool                       (ignoring
polymorphism...)

Is the dot notation the same as conventional functional composition
operator "o" (that is what I was assuming...), your other definitions
seem to imply this.


Trying your example in SML:
- val xx = length o (filter  op=);
stdIn:1.1-40.27 Warning: type vars not generalized because of value
restriction are instantiated to dummy types (X1,X2,...)
val xx = fn : (?.X1 * ?.X1) list -> int

But...
- val xx = length o filter o op=;
stdIn:40.1-40.31 Error: operator and operand don't agree [tycon
mismatch]
operator domain: ('Z list -> int) * (('Y -> bool) -> 'Z list)
operand:         ('Z list -> int) * (('Y -> bool) -> 'Y list -> 'Y
list)
in expression:
length o filter
stdIn:40.1-40.31 Warning: type vars not generalized because of value
restriction are instantiated to dummy types (X1,X2,...)

Thanks for any comments or references!

Sorry that the first post was mangled, from a wrong cut/paste in
editing. Here is the intended posting. (Can't seem to delete original
one from Google groups...)
----------------------------------------------------------------------------
-------------------------------------
I am looking at pointfree notation, which I had previously understood
to be basically just eta-reduction, but now wonder about that
conclusion.

For one example I saw,  (in Haskell)
numOccurrences x = length . filter (== x)
seems fine, but
numOccurrences = (length .) . filter . (==)
worries me.

Seems to me that it wouldn't typecheck. I don't use Haskell (rather
SML), but also assume that all of the functions are curried. Basically
it seems (to me) that the intention is that == should consume only one
argument, and leave its result and the other for filter; i.e. the list
argument is not consumed by the first function in the pipeline (==),
but left for the 2nd (filter)

How would a compiler (interpreter) know about that argument
parcelling, v.s. a strict linear pipeline of arguments?

to restate; if one writes:
h = g . f

How would the compiler know if this is intended to define:
h(x,y) = g( f(x), y)            # as above
or
h(x,y) = g( f(x,y) )            # as in SML

Is the dot notation the same as conventional functional composition
operator "o" (that is what I was assuming...), your other definitions
seem to imply this.

Trying the example in SML:
- val xx = length o (filter  op=);
stdIn:1.1-40.27 Warning: type vars not generalized because of value
restriction are instantiated to dummy types (X1,X2,...)
val xx = fn : (?.X1 * ?.X1) list -> int

But...
- val xx = length o filter o op=;
stdIn:40.1-40.31 Error: operator and operand don't agree [tycon
mismatch]
operator domain: ('Z list -> int) * (('Y -> bool) -> 'Z list)
operand:         ('Z list -> int) * (('Y -> bool) -> 'Y list -> 'Y
list)
in expression:
length o filter
stdIn:40.1-40.31 Warning: type vars not generalized because of value
restriction are instantiated to dummy types (X1,X2,...)

Thanks for any comments or references!

guthrie <guthrie@mum.edu> writes:
> to restate; if one writes:
>       h = g . f
>
> How would the compiler know if this is intended to define:
>    h(x,y) = g( f(x), y)            # as above
> or
>    h(x,y) = g( f(x,y) )            # as in SML

Haskell uses currying for multi-arg functions.  So

h x y = (h x) y =  ((g.f) x) y

> Is the dot notation the same as conventional functional composition
> operator "o"

Yes.

guthrie wrote:
> For one example I saw,  (in Haskell)
>     numOccurrences x = length . filter (== x)
> seems fine, but
>   numOccurrences = (length .) . filter . (==)
> worries me.
>
> Seems to me that it wouldn't typecheck.

Adding parentheses in the right place makes things a little clearer.
Here's the general idea.

(==) has type:   a -> (a -> Bool)
filter has type: (a -> Bool) -> ([a] -> [a])

so, then, by general properties of function composition,

filter . (==) has type: a -> ([a] -> [a])

Now length has type: [a] -> Int, so (length .) is a section that expects
a function from some type to [a], and gives a function from that type to
Int by composing it with length.  That is,

(length .) has type: (b -> [a]) -> (b -> Int)

By unification, this polymorphic type b is matched against [a], so
(length .) specializes to:

([a] -> [a]) -> ([a] -> Int)

and you apply function composition again to get

(length .) . filter . (==) has type a -> ([a] -> Int)

and of course the parentheses are redundant, so this is the same type as
a -> [a] -> Int, as you expect.

> I don't use Haskell (rather
> SML), but also assume that all of the functions are curried.

Correct.  The other thing there that I don't recall seeing in ML (it's
been a while) is sections.  That is, (length .) means the same thing as
((.) length), or (\x -> length . x).

> to restate; if one writes:
>       h = g . f
>
> How would the compiler know if this is intended to define:
>    h(x,y) = g( f(x), y)            # as above
> or
>    h(x,y) = g( f(x,y) )            # as in SML

Function composition is only defined on functions of one argument, so
with curried functions, it's always interpreted as the first statement
above.  If you want the second behavior, then that's not (g . f), but
rather ((g .) . f).  Or, if you want to be less tricky, it's
\x y -> g (f x y).

> Trying the example in SML:
> - val xx = length o filter o op=;
> stdIn:40.1-40.31 Error: operator and operand don't agree [tycon
> mismatch]
>   operator domain: ('Z list -> int) * (('Y -> bool) -> 'Z list) operand:
>           ('Z list -> int) * (('Y -> bool) -> 'Y list -> 'Y list)
>   in expression:
>     length o filter

Perhaps I'm not understanding the syntax here, but it looks like you
didn't type the same thing.  In Haskell:

Prelude> length . filter . (==)

<interactive>:1:9:
Couldn't match expected type `[a]'
against inferred type `[a1] -> [a1]'
In the second argument of `(.)', namely `filter . (==)'
In the expression: length . filter . (==)
In the definition of `it': it = length . filter . (==)

so that doesn't work in Haskell either.  You need partial application of
the function composition operator on length.

On Mar 31, 8:57=A0pm, Chris Smith <cdsm...@twu.net> wrote:
> guthrie wrote: 
> 
>
> Adding parentheses in the right place makes things a little clearer. =A0
> Here's the general idea.
>
> =A0 =A0(=3D=3D) has type: =A0 a -> (a -> Bool)
> =A0 =A0filter has type: (a -> Bool) -> ([a] -> [a])
>
> so, then, by general properties of function composition,
>
> =A0 =A0filter . (=3D=3D) has type: a -> ([a] -> [a])
>
> Now length has type: [a] -> Int, so (length .) is a section that expects
> a function from some type to [a], and gives a function from that type to
> Int by composing it with length. =A0That is,
>
> =A0 =A0(length .) has type: (b -> [a]) -> (b -> Int)
>
> By unification, this polymorphic type b is matched against [a], so
> (length .) specializes to:
>
> =A0 =A0([a] -> [a]) -> ([a] -> Int)
>
> and you apply function composition again to get
>
> =A0 =A0(length .) . filter . (=3D=3D) has type a -> ([a] -> Int)
>
> and of course the parentheses are redundant, so this is the same type as
> a -> [a] -> Int, as you expect.
> 
>
> Correct. =A0The other thing there that I don't recall seeing in ML (it's
> been a while) is sections. =A0That is, (length .) means the same thing as
> ((.) length), or (\x -> length . x).
> 
> 
>
> Function composition is only defined on functions of one argument, so
> with curried functions, it's always interpreted as the first statement
> above. =A0If you want the second behavior, then that's not (g . f), but
> rather ((g .) . f). =A0Or, if you want to be less tricky, it's
> \x y -> g (f x y).
> 
d: 
st) 
>
> Perhaps I'm not understanding the syntax here, but it looks like you
> didn't type the same thing. =A0In Haskell:
>
> Prelude> length . filter . (=3D=3D)
>
> <interactive>:1:9:
> =A0 =A0 Couldn't match expected type `[a]'
> =A0 =A0 =A0 =A0 =A0 =A0against inferred type `[a1] -> [a1]'
> =A0 =A0 In the second argument of `(.)', namely `filter . (=3D=3D)'
> =A0 =A0 In the expression: length . filter . (=3D=3D)
> =A0 =A0 In the definition of `it': it =3D length . filter . (=3D=3D)
>
> so that doesn't work in Haskell either. =A0You need partial application of=[/color
]

> the function composition operator on length.

Hi

Interesting discussion. With Haskell, it seems -- to an admittedly
less than knowledgeable quasi-user -- one can move in the direction of
inventing a Morse-code programming style :D

Anyway, assuming we have the definition of "numOccurences" as

numOccurences   :: Eq a =3D> a -> [a] -> Int
numOccurences   =3D (length .) . filter . (=3D=3D)

=2E..how do we use it to write a one-liner that maps it to a range of
chars representing the alphabet (say "['a'..'z']") to check the string
"supercalifragilisticexpialidocious" and return a list of the
occurrences of all alphabet letters? (Can/should we do it using
"map"?). How do we write a "pointfree" version of this?

--

Also, here's another function:

subElement xs f p i =3D ((filter p . map f) xs)!! i

How would this be rendered "pointfree?"


Thanks.


-- K.E.

KE wrote:
> Anyway, assuming we have the definition of "numOccurences" as
>
>     numOccurences   :: Eq a => a -> [a] -> Int numOccurences   = (length
>     .) . filter . (==)
>
> ...how do we use it to write a one-liner that maps it to a range of
> chars representing the alphabet (say "['a'..'z']") to check the string
> "supercalifragilisticexpialidocious" and return a list of the
> occurrences of all alphabet letters? (Can/should we do it using "map"?).
> How do we write a "pointfree" version of this?

That would be

map (flip numOccurrences "supercala...") ['a'..'z']

> Also, here's another function:
>
>     subElement xs f p i = ((filter p . map f) xs)!! i
>
> How would this be rendered "pointfree?"

In general, if you want to know how to write a pointfree function, you
can ask lambdabot.  The easiest way is to grab an IRC client, go to
irc.freenode.net, and type

/msg lambdabot @pl subElement xs f p i = ((filter p . map f) xs)!! i

You can also install lambdabot locally, if you use it a lot; though the
last time I looked, Linux was a definite prerequisite for that.

In this case the answer is:

subElement = (((!!) .) .) . flip (flip . flip ((.) . filter) . map)

Which is ugly enough that you certainly don't want to write this function
in point-free style.  (Unless, of course, you're trying to start a new
obfuscated code contest for Haskell.)