Higher-order functions with a function using an extensible record?

[Rémi Lefèvre]

Hi,

Does anyone know if there is a way to use higher-order functions with a function using an extensible record?

When I try to build this code:

type alias Named a =
   { a | name : Maybe String }

getName : Named a -> Maybe String
getName { name } =
   name

type Element
   = AnElement { name : Maybe String }
   | AnotherElement { name : Maybe String }

mapNamed : (Named a -> b) -> Element -> b
mapNamed func element =
   case element of
     AnElement e ->
        func e

     AnotherElement e ->
        func e

getElementName : Element -> Maybe String
getElementName e =
   mapNamed getName e


I get the following error:

Detected errors in 1 module. -- TYPE MISMATCH ----------------------------------- Types.elm The argument to function `func` is causing a mismatch. 13| func e ^ Function `func` is expecting the argument to be: Named a But it is: { name : Maybe String } Hint: Your type annotation uses type variable `a` which means any type of value can flow through. Your code is saying it CANNOT be anything though! Maybe change your type annotation to be more specific? Maybe the code has a problem? More at: <https://github.com/elm-lang/elm-compiler/blob/0.18.0/hints/type-annotations.md>

I struggle to understand why this does not work whereas replacing func by getName satisfies the compiler:

getElementName : Element -> Maybe String
getElementName element =
  case element of
  AnElement e ->
  getName e

  AnotherElement e ->
  getName e

Any idea ?

Thank you and sorry if this has been already discussed, I did not find anything.

[Ilias Van Peer]

mapNamed : (Named a -> b) -> Element -> b

In that line, you say that I can pass in a function that works on `Named a`, where `a` isn't bound to anything. So if I were to write a function `foo : Named { iAlsoNeedAnInt : Int } -> Int`, I could pass that to that `mapNamed`. However `Element` contains a very specific type of `Named a` - it is a `Named {}`.

So one thing you could do is changing the annotation to say `mapNamed : (Named {} -> b) -> Element -> b`. Note that this would fall apart as soon as the different values in `Element` actually have different types.

Note that this isn't unique to extensible records, or even records at all. Say you wanted to allow passing `identity` in. You could try `mapNamed : (a -> b) -> Element -> Element`, but that also wouldn't work.. Because I could pass in `(\x -> x * 7)` which has type `number -> number`, which is valid according to the `a -> a` shape.

I hope this clarifies things a little?

Op woensdag 4 oktober 2017 16:19:45 UTC+2 schreef Rémi Lefèvre:

[Rupert Smith]

On Wednesday, October 4, 2017 at 3:19:45 PM UTC+1, Rémi Lefèvre wrote:

When I try to build this code:

type alias Named a =
   { a | name : Maybe String }

getName : Named a -> Maybe String
getName { name } =
   name

type Element
   = AnElement { name : Maybe String }
   | AnotherElement { name : Maybe String }

mapNamed : (Named a -> b) -> Element -> b
mapNamed func element =
   case element of
     AnElement e ->
        func e

     AnotherElement e ->
        func e

getElementName : Element -> Maybe String
getElementName e =
   mapNamed getName e

The Element type here is analogous to object oriented programming - you have a parent type Element, with 2 sub-types AnElement and AnotherElement. Your 'mapNamed' function is like a virtual method - it knows just enough about the overall type of Element to work with all 'sub-types' of it.

As Ilias points out, the type of the records within the Element type is 'Named {}' but the function is of type 'Name a -> b'. So you are thinking that the 'a' variable should get bound to {} when this function is invoked?

This would work in an object oriented language, but not Elm. The reason is that Elm does not support sub-typing at all. Elm has type inference - it looks at the type of function you wrote and deduced that the type of 'func' should be 'Named {} -> b' and finds that it does not match with what you specified in the type signature, so it fails the type checking. 

'Named {}' is a sub-type of 'Named a' in languages that support sub-typing. It makes sense because anywhere you can use a 'Named a', you should also be able to use a more specific type such as 'Named {}' or 'Named Int' or whatever.

Elm has type inference and type inference does not work with sub-typing. The typing problem is semi-decidable. This means that given the type of an expression, it is possible to decide whether or not that is the correct type of the expression. Going the other way, given an expression it is not possible to deduce what the type of that expression should be when sub-typing is allowed in the type system.

It is easy to mistake Elms extensible records for sub-typing, especially if you come from an OO back-ground. It is generally not worth trying to use extensible records at all for data modelling in Elm, because they tend to lead you down this blind alley very quickly. Their use case is for narrowing the exposure of a function to parts of a record it does not care about. I reference Richard Feldman's 2017 Elm Europe talk as a good resource to learn more about this:

https://www.youtube.com/watch?v=DoA4Txr4GUs

The moral of the story is - don't try and do OO programming in Elm, it won't work.

[Rémi Lefèvre]

Thank you very much, this is perfectly clear.

For some reason, I was confused by extensible records and thought I could express a type of functions that are guaranteed to not use any record field not defined by the Named type alias.
Of course this is wrong and consistent with the rest of the language. Actually my contrived example is as absurd as the simpler:

fails : (a -> b) -> b
fails func =
    func ()

life =
    fails (\_ -> 42)

I think that what I confusingly expected of extensible records in this case was more like a typeclass implementing the `.name : a -> Maybe String` operation.
And that's why extensible records are AFAIK only mainly used to narrow functions arguments currently.


So thank you again for having cleared my mind.

[art yerkes]

It's a niggle, but I think it's more correct to say that type inference isn't completely decidable in the presence of subtyping.

[Rupert Smith]

On Sunday, October 8, 2017 at 6:48:39 PM UTC+1, art yerkes wrote:

It's a niggle, but I think it's more correct to say that type inference isn't completely decidable in the presence of subtyping.

Fair enough. Even with subtyping, it is sometimes obvious that a type can still be correctly inferred. Unfortunately, not in the general case.