Proposal: alpha-rename the type signatures of foldl, foldl', and scanl to be consistent with foldr and scanr

[Tyson Whitehead]

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).