[Haskell-cafe] detecting infinite loop with type inference (Was: Why Haskell?)

[Tom Ellis]

It's even better if you generalise merge to

    merge :: Ord a => [a] -> [a] -> [a]                                                                                                
Then the type of sort is Ord a => [b] -> [a] and it's more obvious
that not only is the input unused but the output is always empty.

Interestingly I wrote on article about how to improve a particular
program Mark Dominus himself wrote featuring exactly this kind of
analysis!

    http://h2.jaguarpaw.co.uk/posts/using-brain-less-refactoring-yahtzee/

Tom



On Mon, Mar 29, 2021 at 07:30:41PM +0200, Jaro Reinders wrote:
> I get the same strange inferred type for this quickly translated program:
> 
>     split []      = ([], [])
>     split [h]     = ([h], [])
>     split (x:y:t) = let (s1, s2) = split t
>                     in (x:s1, y:s2)
> 
>     merge :: [Int] -> [Int] -> [Int]
>     merge [] x = x
>     merge x [] = x
>     merge (h1:t1) (h2:t2) =
>       if h1 < h2    then h1:merge t1 (h2:t2)
>                     else h2:merge (h1:t1) t2
> 
>     sort [] = []
>     sort x  = let (p, q) = split x
>               in merge (sort p) (sort q)
> 
> 
> 
>     > :t sort
>     sort :: [a] -> [Int]
> 
> The reason is that sort always returns the empty list, independently of the
> input list, so the type of the input list is not constrained.
> 
> On 29-03-2021 19:13, Henning Thielemann wrote:
> > 
> > On Mon, 29 Mar 2021, Antonio Regidor Garcia wrote:
> > 
> > > Not bussiness oriented, but these two articles are pretty good at
> > > explaining what Haskell and similar languages have to offer:
> > > 
> > > This is brief and centered on Haskell's type system:
> > > 
> > > https://perl.plover.com/yak/typing/notes.html
> > 
> >  From slide 29 on he gives the example that type inference can point him
> > to an infinite loop.
> > 
> > This would not work in Haskell, would it?
> > _______________________________________________
> > Haskell-Cafe mailing list
> > To (un)subscribe, modify options or view archives go to:
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > Only members subscribed via the mailman list are allowed to post.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.