Haskell: a -> a -> ... -> b to [a] -> b

Question

I'm trying to express the following map as a Haskell function:

Given two types a, b consider the family of functions F(a, b) consisting of functions of the type

f :: a -> a -> ... -> a -> b

with n repetitions of a, where n is an integer greater than zero. What I want is to map each function f in F(a, b) to a function f' :: [a] -> b, such that f x1 x2 ... xr = f' [x1, ..., xr], where r is smaller than the number of arguments f takes (i.e. I'm looking for the function listify :: F(a, b) -> ([a] -> b)). If there are more elements than f takes arguments, the additional elements should be discarded:

f :: a -> a -> b
(listify f xs) == (listify f $ take 2 xs)

Furthermore, if the empty listed is passed, any value is acceptable.

I'm of course able to implement this map for functions with a fixed number of arguments (for example: listify :: (a -> a -> b) -> ([a] -> b), etc.), but I couldn't find a way to write a function that does it for all f in F(a, b) simultaneously. Even though Template Haskell is probably able to provide me with the right tools, I'm not interested in such a solution. I want to find some pure "type magic" way to do it.

Does anyone know if that's even possible? Can someone maybe point me in the right direction? Or is this a known "problem" which has been solved billions of times and I'm just unable to find a solution?

You can do this with some `OverlappingInstances` trickery (perhaps even with less controversial extensions), but I doubt it's a good idea. Why don't you just use the list-accepting function as it is? — leftaroundabout, Nov 20 '15 at 20:19
Regarding "Why?": the question whether this is possible or not just popped into my head --> I'm asking for educational reasons (maybe also learn some new Haskell magic, while trying to figure out a solution). I'm a bit confused as to which "list accepting function" you're refering to. I have a function f :: a -> a -> ... a -> b (with a unknown number of 'a's) and want a function f' :: [a] -> b, such that f x1 ... xr = f' [x1, ...., xr]. Thus, I don't have a list accepting function, I want one! But probably I didn't get what you really meant. — morris, Nov 20 '15 at 20:22
What exactly would you do with `OverlappingInstances` to make it work? I don't see any way to do it. — morris, Nov 20 '15 at 20:27
Well, yes, it is possible, it's basically the dual problem to a variadic signature like [`printf`](http://hackage.haskell.org/package/base-4.8.1.0/docs/Text-Printf.html#v:printf). However, this kind of polymorphism often leads to problems. In particular, your proposal circumvents the compiler's type-checking: by deferring a fixed number of arguments to being taken from a runtime-length list, the compiler can't check that there are enough arguments, so you'll need a sensible error case... An application where I could see this useful is parsing, but this is better done with _parser combinators_! — leftaroundabout, Nov 20 '15 at 20:29
With the "to little arugements" you're of course right. I just thought "Well... just return a partly applied function.". But I'm seeing just now, that this of course doesn't type check (maybe even thats possible? I mean returning a partially applied function if the list is too short). Regarding usefulness: I don't really care for applications/usefulness/dangers of such a function. I'm merely interested on how to do it (I'm hoping to acquire some knew Haskell knowledge + I think that `listify` just intersting ;)). — morris, Nov 20 '15 at 20:38

András Kovács · Accepted Answer · 2015-11-20T21:35:45.117

We just have to pick our poison here. If we use less safe pragmas, we can get more inference, and vice versa; there's a number of combinations.

First: uses overlapping instances, has non-functions as base case, but can't handle polymorphic a types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- error
-- listify (+) [0, 2 :: Int] -- OK
-- listify () [] -- OK

Second: uses overlapping instances, has functions as base case, can handle polymorphic types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances, FlexibleContexts #-}

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where
  listify f (a:_) = f a

instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- OK
-- listify () [] -- error, first arg must be a function

Third: uses incoherent instances, has values in base case, can handle polymorphic types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify 0 [] -- OK
-- listify (+) [2, 4] -- OK

Fourth: uses closed type families with UndecidableInstances as helper for instance resolution, has values in base case, can't handle polymorphic types:

{-# LANGUAGE UndecidableInstances, ScopedTypeVariables, DataKinds,
    TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-}

import Data.Proxy

data Nat = Z | S Nat

type family Arity f where
  Arity (a -> b) = S (Arity b)
  Arity b        = Z

class Listify (n :: Nat) a b where
  listify' :: Proxy n -> a -> b

instance r ~ (a -> b) => Listify Z b r where
  listify' _ = const

instance (Listify n f r, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) a r where
  listify' _ f (a:as) = listify' (Proxy :: Proxy n) (f a) as

listify :: forall a b. Listify (Arity a) a b => a -> b
listify = listify' (Proxy :: Proxy (Arity a))

-- listify (+) [3, 4] -- error
-- listify (+) [3, 4::Int] -- OK
-- listify () [] -- OK
-- listify 0 [] -- error
-- listify (0 :: Int) [] -- OK

From the top of my head, roughly these are the variants one can see in the wild, except for the INCOHERENT one, because that's extremely rare in library code (for good reasons).

I personally recommend the version with the closed type families, because UndecidableInstances and type families are by far the least controversial as language extensions, and they still provide a fair amount of usability.

Especially the last one is pretty cool! That's extremeply close to how I imagined it should be (only "flaw" I can see are the explicit type annotations). What is the customary here? If I consider your answer to be better than the previously accepted one, am I allowed/supposed to instead accept yours? — morris, Nov 20 '15 at 21:33
@morris: yes, you're supposed to accept the best answer, not the earliest. — leftaroundabout, Nov 20 '15 at 21:40
@morris: note that in the above solutions we only need type annotations (except with incoherent instances, because there GHC wriggles its way through either way) if the argument type is polymorphic. In the examples, the number literals have polymorphic type `Num a => a`, but it always works with `Bool` annotation-free, for example. — András Kovács, Nov 20 '15 at 21:48
@AndrásKovács : Do you think it's possible to incorporate partial application into `listify`? I mean stuff like `listify (+) [1]` (whoch should be equal to `(+) 1`). — morris, Nov 20 '15 at 21:54
@morris as a general rule you should avoid accepting an answer right away. Wait some time, even 1 day. For a simple reason: once an answer is accepted the chances of receiving other answers go down. But you generally don't know whether there *could* be much better answers than the current one. — Bakuriu, Nov 20 '15 at 21:55

leftaroundabout · Answer 2 · 2015-11-20T20:48:09.163

5

Actually it's quite simple, doesn't even require overlapping instances:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Listifiable f a b where
  listify :: f -> [a] -> b

instance Listifiable b a b where
  listify = const

instance (Listifiable f) a b => Listifiable (a->f) a b where
  listify f (x:xs) = listify (f x) xs

Then you can do

GHCi> listify ((+) :: Int->Int->Int) [1,2 :: Int] :: Int
3

But the need for those local explicit type signatures quite shows the problems you're getting yourself in.

(It might be possible to alleviate this problem with FunctionalDependencies, but at least not in a straightforward way.)

edited Nov 20 '15 at 20:48

answered Nov 20 '15 at 20:41

leftaroundabout

117,950
5
174
319

Thanks for the solution! "need for those local explicit type signatures" yeah thats rather ugly. Do you know if there is any better way to do it? I mean the idea of `f x1 ... xr = f' [x1, ..., xr]` is sound (even with partial application in mind). If there is no way to do that "nicely" in Haskell this would be the first case I experience of "mathematically easily expressed, but very hard to implement" (very hard meaning: either dangerous or just completely ugly). Do you maybe know a language where it can be expressed easily & safely? – morris Nov 20 '15 at 20:54
The problem is that functions with different numbers of arguments have different types, while lists of different length have all the same type. Types only exist at compile time, list-lengths only exist at runtime. — And, no, I don't agree this is “mathematically easily expressed”: _what are_ `f` and `f'` in your statement? What you really mean is, it can be easily expressed in a dynamically-typed language. Well, you can [easily implement a dynamic language in Haskell](https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours)! But you loose all the benefits of static types. – leftaroundabout Nov 20 '15 at 20:59
I can express it as follows. Let X, Y be non empty sets, define Fn indutively as Fn := {X -> F(n-1)}, where F1 := {X -> Y}. Let F be the union of all Fn for n, natural number greater than 0. Furthermore, consider the set L := (union {n = 0, to inf.} X^n) union {N -> X}, where N are the natural numbers (L "=" {[X]}). f in F implies f in An for some n. Define f' : L -> (union {n = 1, to inf.} An) union Y as follows: for each args in L, r := "length" args: f' args := (...(f(args_1))(args_2) ... (args_max(n,r)). This determines f' uniquely & is well defined. – morris Nov 20 '15 at 21:20
Nice. (Not _that_ easy though, is it?) Well, András Kovács demonstrated how to express this unique type-mapping in Haskell with either `OverlappingInstances` or closed type families (which really does look a lot like your mathematical definition). I persist, however, that you should probably better avoid all of this, by simply not listifying your functions... – leftaroundabout Nov 20 '15 at 21:35
The formalized version probably looks a lot cleaner/easier in "non ASCII math" ; ) - I can not even see a single sane reason to listify my functions; probably code golf could in some circumstances be a reason if "listify" was part of the standard library (meaning: safe & easy to use). – morris Nov 20 '15 at 21:40

Haskell: a -> a -> ... -> b to [a] -> b

2 Answers2