Can you create functions that return functions of a dependent arity in a dependently typed language?

Question

From what I know about dependent types, I think that it should possible, but I've never seen an example of this before in a dependently typed language, so I'm not exactly sure where to start.

What I want is a function of the form:

f : [Int] -> (Int -> Bool)
f : [Int] -> (Int -> Int -> Bool)
f : [Int] -> (Int -> Int -> Int -> Bool)

etc...

This function takes a list of n Ints, and returns a predicate function of arity n that takes Ints as an argument. Is this sort of thing possible in a dependently typed language? How would something like this be implemented?

Answer 1

When creating functions of varying arity, you generally need a function from values to types. In this case, we need a function from List ℕ (or simply ℕ - the length of the list) to Set:

Predicate : ℕ → Set
Predicate zero    = Bool
Predicate (suc n) = ℕ → Predicate n

This allows us to create different type for each number:

Predicate 0 = Bool
Predicate 1 = ℕ → Bool
Predicate 2 = ℕ → ℕ → Bool
-- and so on

---

Now, how do we use Predicate to express the type of f? Since we are in dependently typed language, we can freely use value-level functions in types. So length seems to be a natural fit:

f : (l : List ℕ) → Predicate (length l)

Now, you didn't specify any particular f, but for the sake of the example, I'm going to implement one. Let's say that we want to check if all the numbers at corresponding positions (i.e. 1st argument to the function with 1st element of the list and so on) are equal.

I picked a rather simple function, so the implementation will be quite straightforward. But note that these kinds of functions use various tricks not unlike those used for implementing variadic functions with type classes (in Haskell).

When given an empty list, we'll simply return true:

f []       = true

For the nonempty list case, we create a function taking one argument named n and then compare it to the head of the list (m). If those numbers are not equal, we'll shortcut the rest of f and return a function that ignores all other numbers and simply returns false; if those numbers are equal, we'll simply continue with the rest of the list:

f (m ∷ ms) = λ n → case m ≟ n of λ
  { (yes _) → f ms
  ; (no  _) → always-false
  }

And the helper function always-false:

always-false : ∀ {n} → Predicate n
always-false {zero}  = false
always-false {suc _} = λ _ → always-false

And here's how you'd use it:

test : Bool
test = f (1 ∷ 2 ∷ 3 ∷ []) 1 2 4  -- false

---

As a final remark: those functions are not very useful when you do not have any information about the argument you are applying it to. For example, if you use f on a list of unknown length (that was given as an argument to another function), you can't even apply the "predicate" to a number. It's quite possible that the list is empty in which case the predicate is Bool and cannot be applied to anything.

Answer 2

@Vitus already proposed an Agda solution using dependent types. Here I'm commenting on Haskell instead, since you added its tag.

In Haskell we haven't dependent types as in Agda, so we can't write length l in the type. We can however use a custom list GADT, which exposes the length of the list at the type level, using Peano naturals.

data Z
data S n

data List n a where
   Nil :: List Z a
   Cons :: a -> List n a -> List (S n) a

Then, we can use a type family to compute the type (a -> a -> ... -> Bool) having n arguments, where n is a given type-level natural.

type family Fun n a
type instance Fun Z     a = Bool
type instance Fun (S n) a = a -> Fun n a

Here's how you use it. The following compares the list to the "list of arguments" provided.

equalityTest :: Eq a => List n a -> Fun n a
equalityTest = go True
  where go :: Eq a => Bool -> List n a -> Fun n a
        go b Nil = b
        go b (Cons x xs) = \y -> go (x==y && b) xs

-- *ListGADT> equalityTest (Cons 1 (Cons 2 Nil)) 1 2
-- True
-- *ListGADT> equalityTest (Cons 1 (Cons 2 Nil)) 1 3
-- False