Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generate function of given arity in Haskell using type numbers

Assume I have encoded the natural numbers in Haskell types, and that I have a way of adding and subtracting from them:

data Zero
data Succ n
-- ...

I have seen various bits of code which create the appearance of variadic functions, such as this, which allows the following:

buildList "polyvariadic" "function" "wut?" :: [String]
-- ["polyvariadic","function","wut?"]

What I am wondering is whether I can build off of that to make a function which will only accept the number of arguments that corresponds to an instance of a type number. What I'm trying to do would look something like:

one = Succ Zero
two = Succ one
three = Succ two

threeStrings :: String -> String -> String -> [String]
threeStrings = buildList three

threeStrings "asdf" "asdf" "asdf"
-- => ["asdf","asdf","asdf"]

threeStrings "asdf"
-- type checker is all HOLY CHRIST TYPE ERROR

threeStrings "asdf" "asdf" "asdf" "asdf"
-- type checker is all SWEET JESUS WHAT YOU ARE DOING

I'm aware that this is pretty silly and that it's probably a waste of my time, but it seemed like something that would be fun for the weekend.

like image 797
Jonathan Sterling Avatar asked May 03 '11 00:05

Jonathan Sterling


People also ask

Which function is used to find type signature in Haskell?

We thus see that we make use of two functions here: (&&) :: Bool -> Bool -> Bool , and elem :: (Eq e, Foldable f) => e -> f e -> Bool , we here use e instead of f to avoid "name clashes" with our already defined type variable a .

What is fixed arity?

Fixed arity function is the most popular kind present in almos tall programming languages. Fixed arity function must be called with the same number of arguments as the number of parameters specified in its declaration. Definite arity function must be called with a finite number of arguments. fun sum(a:Int, b:Int) {

What is arity in Python?

Arity, in a python functional sense, refers to the number of arguments that the function takes. In the cases above, all of the functions require two arguments, and thus have an arity of two.


1 Answers

OK. Yes. Definitely, by threading a numeric type around the recursive instances.

First, some boilerplate:

{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses  #-}
{-# LANGUAGE EmptyDataDecls         #-}
{-# LANGUAGE FlexibleInstances      #-}
{-# LANGUAGE FlexibleContexts       #-}
{-# LANGUAGE ScopedTypeVariables    #-}

Your nats:

data Zero
data Succ n

A recursive builder for the variadic functions, now with an n argument:

class BuildList n a r | r -> a where
    build' :: n -> [a] -> a -> r

A base case: stop when we get to Zero:

instance BuildList Zero a [a] where
    build' _ l x = reverse $ x:l

Otherwise, decrement by one and recurse:

instance BuildList n a r => BuildList (Succ n) a (a->r) where
    build' (_ :: Succ n) l x y = build' (undefined :: n) (x:l) y

Now, we only want to loop 3 times, so write that down:

build :: BuildList (Succ (Succ Zero)) a r => a -> r
build x = build' (undefined :: Succ (Succ Zero)) [] x

Done.

Testing:

> build "one" "two" "three" :: [[Char]]
["one","two","three"]

Any less or more are errors:

*Main> build "one" "two" "three" "four" :: [[Char]]

<interactive>:1:1:
    No instance for (BuildList Zero [Char] ([Char] -> [[Char]]))

*Main> build "one" "two" :: [[Char]]

<interactive>:1:1:
    No instance for (BuildList (Succ Zero) [Char] [[Char]])
like image 177
Don Stewart Avatar answered Oct 22 '22 15:10

Don Stewart