3 ms·

I just asked Gemini 2.5 Pro to write a function in Haskell to partition a list in linear time, and it did it perfectly. When you say you were using ChatGPT and

I just asked Gemini 2.5 Pro to write a function in Haskell to partition a list in linear time, and it did it perfectly. When you say you were using ChatGPT and Claude, do you mean you were using the free ones? Plain GPT 4o is very poor at coding. -- | Takes a predicate and a list, and returns a pair of lists. -- | The first list contains elements that satisfy the predicate. -- | The second contains the rest. partitionRecursive :: (a -> Bool) -> [a] -> ([a], [a]) partitionRecursive _ [] = ([], []) -- Base case: An empty list results in two empty lists. partitionRecursive p (x:xs) = -- Recursively partition the rest of the list let (trues, falses) = partitionRecursive p xs in if p x -- If the predicate is true for x, add it to the 'trues' list. then (x : trues, falses) -- Otherwise, add it to the 'falses' list. else (trues, x : falses)

zelphirkalt 1y ago
My Haskell reading is weak, but that looks like it would change the order of elements in the 2 lists, as you are prepending items to the front of `trues` and `falses`, instead of "appending" them. Of course `append` is forbidden, because it is linear runtime itself. I just checked my code and while I think the partition example still shows the problem, the problem I used to check is a similar one, but different one: Split a list at an element that satisfies a predicate. Here is some code for that in Scheme: (define split-at (λ (lst pred) "Each element of LST is checked using the predicate. If the predicate is satisfied for an element, then that element will be seen as the separator. Return 2 values: The split off part and the remaining part of the list LST." (let iter ([lst° lst] [index° 0] [cont (λ (acc-split-off rem-lst) (values acc-split-off rem-lst))]) (cond [(null? lst°) (cont '() lst°)] [(pred (car lst°) index°) (cont '() (cdr lst°))] [else (iter (cdr lst°) (+ index° 1) (λ (new-tail rem-lst) (cont (cons (car lst°) new-tail) rem-lst)))])))) For this kind of stuff with constructed continuations they somehow never get it. They will do `reverse` and `list->vector`, and `append` all day long or some other attempt of working around what you specify they shall not do. The concept of building up a continuation seems completely unknown to them.

zelphirkalt 1y ago

My Haskell reading is weak, but that looks like it would change the order of elements in the 2 lists, as you are prepending items to the front of `trues` and `falses`, instead of "appending" them. Of course `append` is forbidden, because it is linear runtime itself. I just checked my code and while I think the partition example still shows the problem, the problem I used to check is a similar one, but different one: Split a list at an element that satisfies a predicate. Here is some code for that in Scheme: (define split-at (λ (lst pred) "Each element of LST is checked using the predicate. If the predicate is satisfied for an element, then that element will be seen as the separator. Return 2 values: The split off part and the remaining part of the list LST." (let iter ([lst° lst] [index° 0] [cont (λ (acc-split-off rem-lst) (values acc-split-off rem-lst))]) (cond [(null? lst°) (cont '() lst°)] [(pred (car lst°) index°) (cont '() (cdr lst°))] [else (iter (cdr lst°) (+ index° 1) (λ (new-tail rem-lst) (cont (cons (car lst°) new-tail) rem-lst)))])))) For this kind of stuff with constructed continuations they somehow never get it. They will do `reverse` and `list->vector`, and `append` all day long or some other attempt of working around what you specify they shall not do. The concept of building up a continuation seems completely unknown to them.