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.
|
