User:Hakerh400/Flexible dependencies in Haskell

It is well known that in Haskell there is no easy way to put functions that depend on each other into seperate files. The reason is because Haskell does not allow circular imports (like in Node.js) or header files (like in C). GHC supports hs-boot file that in some sense acts as a header file and allows mutually dependent functions to be in separate files, but it is seems excessively complicated for such a basic functionality and requires extra setup and maintenance effort.

In this article we explain a very simple way to put mutually dependent functions in deparate files and don't every worry in which file which function is. The key is to use undecidable instances with functional dependencies and string kinds as function names. Here is an example:

Main.hs

{-# LANGUAGE DataKinds #-}

import Base
import A
import B

main :: IO ()
main = print (call @"func_a" 5)

Base.hs

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE FunctionalDependencies #-}

module Base where
import GHC.Types

class Base (name :: Symbol) (t :: Type) | name -> t where
  call :: t

A.hs

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE UndecidableInstances #-}

module A where
import Base

instance (Base "func_b" (Int -> Int)) => Base "func_a" (Int -> Int) where
  call n = if n <= 1 then 1 else call @"func_b" n

B.hs

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE UndecidableInstances #-}

module B where
import Base

instance (Base "func_a" (Int -> Int)) => Base "func_b" (Int -> Int) where
  call n = n * call @"func_a" (n - 1)

This example shows two mutually recursive functions func_a and func_b. They are in files A.hs and B.hs respectively, and they do not know of each other at the time of compiling corresponding files. However, when compiling Main.hs, both function can be called. In this case, func_a computes the factorial of a number.

The only problem is that all dependencies must be mentioned in the instance context. The solution is to use type synonym when the number of dependencies becomes large:

type Ctx =
  ( Base "add" (Int -> Int -> Int)
  , Base "negate" (Int -> Int)
  , Base "show_int" (Int -> String)
  )

instance Ctx => ...