[Haskell-cafe] GPT & Haskell

[Levent Erkok]

This code is buggy when lo + hi overflows your integer type. Classic (extremely) corner  case bug: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

> On Mar 31, 2023, at 1:02 PM, Gregory Guthrie <guthrie at miu.edu> wrote:
> 
> From a colleague:
>   GPT Pretty smart(?!).
> But this is of course simple, and searchable.
>  
> Still…
> --------------------------------------------------------------------------------------------------
> GPT-4 when prompted:
> 
> Write binary search in Haskel. Print results using putStrLn. Ensure bug-free code by specifying preconditions, postconditions, invariants, variants, internal states.
>  
> gives the following response:
> 
> -- Binary search in Haskell
> -- Precondition: the list is sorted in ascending order
> -- Postcondition: the function returns the index of the target element if found, or Nothing otherwise
> -- Invariant: the search space is always within the bounds of the list
> -- Variant: the search space decreases by half at each recursive call
> -- Internal state: the lower and upper bounds of the search space
> 
> binarySearch :: Ord a => [a] -> a -> Maybe Int
> binarySearch xs x = go xs x 0 (length xs - 1)
>   where
>     go xs x lo hi
>       | lo > hi = Nothing -- base case: search space is empty
>       | x == midElem = Just mid -- base case: target element is found
>       | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half
>       | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half
>       where
>         mid = (lo + hi) `div` 2 -- calculate the middle index
>         midElem = xs !! mid -- get the middle element
> 
> -- Print results using putStrLn
> main :: IO ()
> main = do
>   let xs = [1, 3, 5, 7, 9] -- a sorted list of integers
>   let x = 5 -- a target element to search for
>   let result = binarySearch xs x -- call the binary search function
>   case result of -- pattern match on the result
>     Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned
>     Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned
>  
> The above code runs:
> 
> https://onecompiler.com/cpp/3z48yt2pp
>  
>  
> <image001.png>
>  
> _______________________________________________
> 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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20230331/a97f6caa/attachment.html>