<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">This code is buggy when lo + hi overflows your integer type. Classic (extremely) corner case bug: <a href="https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html">https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html</a><br><div><br><blockquote type="cite"><div>On Mar 31, 2023, at 1:02 PM, Gregory Guthrie <guthrie@miu.edu> wrote:</div><br class="Apple-interchange-newline"><div><meta charset="UTF-8"><div class="WordSection1" style="page: WordSection1; caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;">From a colleague:<o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"> GPT Pretty smart(?!).<o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;">But this is of course simple, and searchable.<o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;">Still…<o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;">--------------------------------------------------------------------------------------------------<o:p></o:p></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 11pt; font-family: Calibri, sans-serif;">GPT-4 when prompted:<o:p></o:p></p><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><b>Write binary search in Haskel. Print results using putStrLn. Ensure bug-free code by specifying preconditions, postconditions, invariants, variants, internal states.</b><o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 11pt; font-family: Calibri, sans-serif;">gives the following response:<o:p></o:p></p><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><b>-- Binary search in Haskell<br>-- Precondition: the list is sorted in ascending order<br>-- Postcondition: the function returns the index of the target element if found, or Nothing otherwise<br>-- Invariant: the search space is always within the bounds of the list<br>-- Variant: the search space decreases by half at each recursive call<br>-- Internal state: the lower and upper bounds of the search space<br><br>binarySearch :: Ord a => [a] -> a -> Maybe Int<br>binarySearch xs x = go xs x 0 (length xs - 1)<br> where<br> go xs x lo hi<br> | lo > hi = Nothing -- base case: search space is empty<br> | x == midElem = Just mid -- base case: target element is found<br> | x < midElem = go xs x lo (mid - 1) -- recursive case: search in the left half<br> | otherwise = go xs x (mid + 1) hi -- recursive case: search in the right half<br> where<br> mid = (lo + hi) `div` 2 -- calculate the middle index<br> midElem = xs !! mid -- get the middle element<br><br>-- Print results using putStrLn<br>main :: IO ()<br>main = do<br> let xs = [1, 3, 5, 7, 9] -- a sorted list of integers<br> let x = 5 -- a target element to search for<br> let result = binarySearch xs x -- call the binary search function<br> case result of -- pattern match on the result<br> Nothing -> putStrLn "Element not found" -- print a message if Nothing is returned<br> Just i -> putStrLn $ "Element found at index " ++ show i -- print a message with the index if Just i is returned</b><o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 11pt; font-family: Calibri, sans-serif;">The above code runs:<o:p></o:p></p><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><b><a href="https://onecompiler.com/cpp/3z48yt2pp" target="_blank" style="color: rgb(5, 99, 193); text-decoration: underline;">https://onecompiler.com/cpp/3z48yt2pp</a></b><o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><span id="cid:image001.png@01D963E1.B0EB6AB0"><image001.png></span><o:p></o:p></div><div style="margin: 0in; font-size: 11pt; font-family: Calibri, sans-serif;"><o:p> </o:p></div></div><span style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;">_______________________________________________</span><br style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><span style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;">Haskell-Cafe mailing list</span><br style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><span style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;">To (un)subscribe, modify options or view archives go to:</span><br style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><span style="caret-color: rgb(0, 0, 0); font-family: SFHello-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;">Only members subscribed via the mailman list are allowed to post.</span></div></blockquote></div><br></body></html>