Retail typing idea.

Retail.md

#Retail typing In which I describe an idea I had for a type system. Or something.

##Intro: Duck typing Duck typing (as in, "if it quacks like a duck...") typically refers to a specific sort of dynamic typing common in dynamically typed, object oriented languages. As an example, consider ruby:

def foo(arg)
  arg.bar.baz
end

We can ask ourselves, what objects does foo work on? And the answer is, anything that defines a method bar, and for which bar returns an object defining a method baz. We don't care about the behaviour of bar and baz, only that they exist. The advantage of this system is that, as new classes are added, they can define a fitting bar, and foo will automatically work for them. The disadvantage(such as it is) is that it's difficult to fit this into a traditional static type system(although, look into row polymorhpism).

##Ruby, dynamic:

class Store
  def init(vals=[])
    @vals = vals
  end
  :attr_accessor vals
  def with_method(method)
   @vals.select{|x| x.methods.include? method}
  end
end

##Haskell version 1

--(with implicit existential quantification)
data Method a = Method (Type b) (a->b) --where Type b is some sort of type tag
data Object = Object a [(String, Method a)]
data Store = Store [Object]
hasMethod m (Object _ methods) = any ((==m) . fst) methods
withMethod m (Store objs) = filter (hasMethod m) objs

Problems with the haskell version:

• Objects returned are dynamic, we can't implicitly utilize the fact that we know they define method f
• Retail typing can't be applied to return types: methods return normal values. No "layering"
• Clunky and weird, we have to basically give up static typing to use it.

##Haskell version 2

data Method a = Method (Type b) (a -> b)
data Object = Object a [(String, Method a)]
data Store = Store [Object]
hasMethod :: String -> Type t -> Object -> Bool
hasMethod m t (Object _ methods) = any (\(s, Method t' _) -> s == m && t == t') methods
withMethod m t (Store objs) = filter (hasMethod m) objs

This allows us to query based on the return type of the methods, which is useful. We can make it a bit nicer:

getMethod :: String -> Type t -> (Object -> Maybe t)
getMethod s t (Object a methods) = fmap ($a) method
  where method = (\(_, Method _ f) -> f) <$> find (\(s', Method t' f) -> s == s' && t == t') methods
withMethod m t (Store objs) = (filter (hasMethod m) objs, fromJust . getMethod m t)

Which also returns the method as a function which can be applied to the objects. The problem with this is that it doesn't prevent you from then applying that function to objects on which it won't work. We could fix this by just applying it ourselves:

withMethod m t (Store objs) = fromJust . getMethod m t <$> filter (hasMethod m) objs

This, however creates the problem that we can't see which object returned which value. If we have two methods, there's no way to look at the objects that define both, and get the pairs resulting from applying each.

##Haskell version 3

data Method a = Method (a -> Object) --where Type b is some sort of type tag
data Object = Object a [(String, Method a)]
data Store = Store [Object]
hasMethod m (Object _ methods) = any ((==m) . fst) methods
mapMethod m (Store objs) = Store $ mapMaybe method objs
  where method (Object a ms) = ($a) <$> find ((==m) . fst) ms

This refines #1 in a different way, making methods Object -> Object and replacing withMethod with a "map", which filters out all the objects not defining a method, applies it to the ones it can, and returns the resulting store. This allows us to compose methods more easily, but makes it difficult to take values out of the heterogenous blob and into the static system.