<div dir="auto">Isn’t binary search useless for lists? It performs worse than full list traversal.</div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Сб, 1 апр. 2023 г. в 03:43, Branimir Maksimovic <<a href="mailto:branimir.maksimovic@gmail.com">branimir.maksimovic@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="line-break:after-white-space">I was thoughtt from my mathematic logic proffesor in 1987 that algorithm for making algorithms<div>doesn’t exist. He proved that there is no algorihm for provin hieor order logic formulas…</div><div><br></div><div>Greets, Branmir.</div></div><div style="line-break:after-white-space"><div><br><div><div><br><blockquote type="cite"><div>On 31. 3. 2023., at 23:37, Yasuaki Kudo <<a href="mailto:yasu@yasuaki.com" target="_blank">yasu@yasuaki.com</a>> wrote:</div><br><div><div dir="auto"><div dir="ltr"></div><div dir="ltr">I am really curious - is it possible to create a programming language designed from the ground up to be used by GPT and similar tools?</div><div dir="ltr"><br></div><div dir="ltr">- Easy to specify the desired outcome</div><div dir="ltr">- Easy to verify results</div><div dir="ltr"><br></div><div dir="ltr">I tried GPT4 to produce COQ proofs of Yoneda Lemma but it could not even complete the interfaces (without implementation) - they failed to compile, by being tripped up by implicit parameters etc.</div><div dir="ltr"><br></div><div dir="ltr">But GPT4 gets much closer to completion compared to GPT3.5</div><div dir="ltr"><br></div><div dir="ltr">I wonder what "GPT-native" programming language might look like😄</div><div dir="ltr"><br></div><div dir="ltr">-Yasu</div><div dir="ltr"><br></div><div dir="ltr"><br></div><div dir="ltr"><br><blockquote type="cite">On Apr 1, 2023, at 06:24, Levent Erkok <<a href="mailto:erkokl@gmail.com" target="_blank">erkokl@gmail.com</a>> wrote:<br><br></blockquote></div><blockquote type="cite"><div dir="ltr">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" target="_blank">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 <<a href="mailto:guthrie@miu.edu" target="_blank">guthrie@miu.edu</a>> wrote:</div><br><div><div style="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;text-decoration:none"><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif">From a colleague:<u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"> GPT Pretty smart(?!).<u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif">But this is of course simple, and searchable.<u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif">Still…<u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif">--------------------------------------------------------------------------------------------------<u></u><u></u></div><p class="MsoNormal" style="margin:0in 0in 12pt;font-size:11pt;font-family:Calibri,sans-serif">GPT-4 when prompted:<u></u><u></u></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><u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div><p class="MsoNormal" style="margin:0in 0in 12pt;font-size:11pt;font-family:Calibri,sans-serif">gives the following response:<u></u><u></u></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><u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div><p class="MsoNormal" style="margin:0in 0in 12pt;font-size:11pt;font-family:Calibri,sans-serif">The above code runs:<u></u><u></u></p><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><b><a href="https://onecompiler.com/cpp/3z48yt2pp" style="color:rgb(5,99,193);text-decoration:underline" target="_blank">https://onecompiler.com/cpp/3z48yt2pp</a></b><u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><span id="m_-4047222526348405260cid:image001.png@01D963E1.B0EB6AB0"><image001.png></span><u></u><u></u></div><div style="margin:0in;font-size:11pt;font-family:Calibri,sans-serif"><u></u> <u></u></div></div><span style="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;text-decoration:none;float:none;display:inline!important">_______________________________________________</span><br style="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;text-decoration:none"><span style="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;text-decoration:none;float:none;display:inline!important">Haskell-Cafe mailing list</span><br style="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;text-decoration:none"><span style="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;text-decoration:none;float:none;display:inline!important">To (un)subscribe, modify options or view archives go to:</span><br style="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;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;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br style="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;text-decoration:none"><span style="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;text-decoration:none;float:none;display:inline!important">Only members subscribed via the mailman list are allowed to post.</span></div></blockquote></div><br><span>_______________________________________________</span><br><span>Haskell-Cafe mailing list</span><br><span>To (un)subscribe, modify options or view archives go to:</span><br><span><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a></span><br><span>Only members subscribed via the mailman list are allowed to post.</span></div></blockquote></div>_______________________________________________<br>Haskell-Cafe mailing list<br>To (un)subscribe, modify options or view archives go to:<br><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>Only members subscribed via the mailman list are allowed to post.</div></blockquote></div><br></div></div></div>_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div>