5

Consider this function:

doToBoth f x y = (f x, f y)

It works as expected in simple cases:

doToBoth (2 *) 10 15 == (20, 30)
doToBoth head [1,2] [3,4,5] == (1, 3)

Then I tried these ones:

doToBoth head [1,10,100] "apple"
doToBoth pred 2 'b'

I want those to both result in (1, 'a'), but instead they just result in a type error. The problem is that the inferred type of doToBoth isn't polymorphic enough:

doToBoth :: (a1 -> a2) -> a1 -> a1 -> (a2, a2)

Seeing this, I tried adding an explicit type signature to fix it:

doToBoth :: (t ~ (i1 -> o1), t ~ (i2 -> o2)) => t -> i1 -> i2 -> (o1, o2)

This type signature was accepted, but it didn't fix the problem, and checking what happened with :t doToBoth revealed that it ended up with a type equivalent to the original inferred one:

doToBoth :: (i2 -> o2) -> i2 -> i2 -> (o2, o2)

What is the correct way to write a type signature to make this function work the way I want?

Improve this question
2
  • ^ You can let me know if that doesn't fully answer your question. It should be a somewhat smallish modification to get something that fulfills your specific question here, but I could give more details on that modification if you'd like. Commented Jan 12, 2019 at 21:33
  • @DavidYoung Your answer there looks almost perfect. It was fairly straightforward to convert it to use visible type applications instead of proxies and to add a new class/instance to support the head function (I can edit either or both of those into your answer there if you want). The only wart about it is that it doesn't really work on the length function, but rather on the function length . toList. I tried for a little while to fix that with the various new GHC extensions since you wrote that back in 2015, but with no luck. Commented Jan 14, 2019 at 3:50

1 Answer 1

Reset to default
5

Accepting a polymorphic argument makes your function rank-2 polymorphic. GHC has an extension for that, but you can only use it if you can somehow quantify over what kinds of types the argument must support – with type constructors or -classes. For instance, for the case of lists you could write

{-# LANGUAGE Rank2Types, UnicodeSyntax #-}
doToBoth_listelem :: (∀ x . [x] -> x) -> [a] -> [b] -> (a,b)
doToBoth_listelem f x y = (f x, f y)

> doToBoth_listelem head [1,10,100] "apple"
(1,'a')

This would also work for the pred example, and is somewhat more useful. In this case you need to quantify over an argument that's constrained by the Enum class:

doToBoth_enum :: (Enum a, Enum b)
      => (∀ x . Enum x => x -> x) -> a -> b -> (a,b)
doToBoth_enum f x y = (f x, f y)

> doToBoth_enum pred 2 'b'
(1,'a')

Writing it so it automatically works for any such constraint that the argument might require is, I think, not possible. It might be possible to approximate that with some clever type families and constraint kinds, but I doubt it would end up being practically usable.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

With the solution you describe, it seems like for every different type of f, I'd need a different version of doToBoth for it, which isn't very convenient. What I really want is what you say is impossible or at least impractical in your last paragraph. I'll leave this open for a few days in case anyone else can think of a way to do it, or for an answer that explains what's missing from Haskell's type system that makes it impossible.
@JosephSible I can't find a general way to do that, unless I exploit intersection types, which are not available in Haskell (IIRC, inference is undecidable with intersection types, and type checking is too expensive). I think you need something like doBoth :: ((a->a') && (b->b')) -> a -> b -> (a', b'), which Haskell does not have.
I wanted to write forall c. (c a, c b) => (forall x. c x => x -> x) -> a -> b -> (a, b), but that didn’t work. I found sort of a way to do it with ConstraintKinds if you pass the dictionaries explicitly, but it’s not worth the trouble: given both :: forall a b c. Dict (c a) -> Dict (c b) -> (forall x. Dict (c x) -> x -> x) -> a -> b -> (a, b) you invoke it as both (Dict :: Dict (Enum Int)) (Dict :: Dict (Enum Char)) (\ Dict -> pred) 2 'b'. Might be a starting point for something more clever though.
@JonPurdy That looks like it would only work when f is an endomorphism, which head isn't.
@JosephSible: Right, was just going off the second example in this answer (doToBoth_enum)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.