Search code examples
haskelltypesinverse

Is it possible to write a function in haskell: (r -> [a]) -> [r -> a])?


Its inverse seems possible. Since I imagine lists are products and -> is exponentiation, (a*a*a...)^r = (a^r)*(a^r)....

Since we can define the inverse [a->r] -> a -> [r] shouldn't it be possible to define this?


Solution

  • If you're willing to fix the size of the list of functions then it'll work.

    dn :: [r -> a] -> (r -> [a])
    dn fns r = map ($ r)
    
    up :: Int -> (r -> [a]) -> [r -> a]
    up n f = tabulate n (\i r -> f' r !! i)
      where 
       f' = cycle . f
       tabulate n f = map f [0..n-1]
    

    Now we can get up as the "sort of" left inverse of dn... provided we shuffle around some length information:

    id1 :: [r -> a] -> [r -> a]
    id1 ls = up (length ls) (dn ls)
    

    and it can be the "sort of" right inverse of dn if we magically know (a) that for every r the length of the result list [a] is the same and (b) we know that length (called magic below)

    id2 :: (a -> [b]) -> a -> [b]
    id2 f = dn . up magic
    

    This answer is basically equivalent to copumpkins comment on leftroundabout's answer, but instead of carrying it out using types I'm passing around the (fixed) length information manually. If you play with up and dn for a bit you'll see why this kind of thing won't work for lists in general.