On October 15, 2012 13:46:53 Dan Burton wrote:
After looking over the type signatures of Data.List, I propose the following "rule of thumb":
When the final result type (the one at the end of a chain of arrows) of a function is a single polymorphic type with no additional structure (e.g. just "a" not "[a]" or "Maybe a"), and the type signature of the function involves more than one type variable, then the type variable appearing in the final position should be "r". (If there is just one type variable, then it should be "a")
...
Another potential reason to dislike this proposal is that GHCi will not follow this convention, and thus will not suggest the same type signature. (Although it could be made to, since I believe I have specified a precise algorithm.)
Talking about algorithms, I was working on a draft paper awhile back assigning measures to types based on their shapes (if you do read it, please note that 2.1 feels right to me, 2.2 is okay, and 2.3 needs more thought). http://www.sharcnet.ca/~tyson/haskell/papers/TypeShape.pdf One of the things coming out of this, I believe, was a fairly strong argument that the key feature of a type (without a higher understanding) is the number of occurances its elementary components make. To this end, I would suggest the following algorithmic approach (I don't actually have an particular reason for the sub-sort in (3) other than some choice has to be made) 1 - count the number of occurances of each free variable, 2 - sort them from most frequently occuring to least, 3 - sub-sort ones of the same frequency according to order of appearance, and 4 - assign the names a, b, c, ... according to the sorted order. For example, under this algorithm, the canonical form of these signatures Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a Prelude.scanl :: (a -> b -> a) -> a -> [b] -> [a] Data.List.foldl' :: (a -> b -> a) -> a -> [b] -> a Data.Foldable.foldl :: Foldable t => (a -> b -> a) -> a -> t b -> a Data.Foldable.foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) genericLength :: Num i => [b] -> i genericSplitAt :: Integral i => i -> [b] -> ([b], [b]) genericIndex :: Integral a => [b] -> a -> b would be (note that I'm counting constraints occurances too) Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a Prelude.scanl :: (a -> b -> a) -> a -> [b] -> [a] Data.List.foldl' :: (a -> b -> a) -> a -> [b] -> a Data.Foldable.foldl :: Foldable b => (a -> c -> a) -> a -> b c -> a Data.Foldable.foldl' :: Foldable b => (a -> c -> a) -> a -> b c -> a mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c]) mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c]) genericLength :: Num a => [b] -> a genericSplitAt :: Integral b => b -> [a] -> ([a], [a]) genericIndex :: Integral a => [b] -> a -> b Not perfect for sure, but not too bad for a pretty dumb algorithm I think. Cheers! -Tyson PS: Actually (disclaimer that I haven't though alot about this yet), I expect that this is the best dumb algorithm possible ignoring possible sub-sort variants (i.e., humans would rank it's output as preferred most often over a large enough random set of actual types).