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

[Jaro Reinders]

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.