4 ms·

> Even a simple thing like concatenation of two lists, that in Prolog it could be done purely declaratively, without expressing how it needs to be performed, se

• junke 7y ago
  What is magical apart from pattern matching is how you can invocate it with mixed ground terms and variables, and it computes values that makes the relationship holds. For example: [eclipse 2]: concat(A,[_,_],[0,1,2,3,4]). A = [0, 1, 2] Yes (0.00s cpu, solution 1, maybe more) ? ; No (0.00s cpu) Or iterate over all lists that concatenate as [0,1,2] [eclipse 3]: concat(A,B,[0,1,2]). A = [] B = [0, 1, 2] Yes (0.00s cpu, solution 1, maybe more) ? ; A = [0] B = [1, 2] Yes (0.00s cpu, solution 2, maybe more) ? ; A = [0, 1] B = [2] Yes (0.00s cpu, solution 3, maybe more) ? ; A = [0, 1, 2] B = [] Yes (0.00s cpu, solution 4)
• ookdatnog 7y ago
  As far as I (not a Prolog expert) know, your Prolog is idiomatic. But it is more declarative than your Haskell or Scheme implementations: you didn't just define a concat function, but a concat relation, which means you can use it in many more ways. Here are just a few examples from the top of my head. - The head function (with X unknown and L known): concat([X],_,L). - Produce all splits of a list (with X and Y unknown): concat(X,Y,L). - Does this list start with the prefix [a,b]? If yes, let Y be the tail (Y unknown): concat([a,b],Y,L). ... and many more.
  • mturmon 7y ago
    This is one of the most magical things about Prolog. From my functional/imperative programming experience, when originally picking up Prolog, I conceptualized the kind of operations you describe (e.g., “all splits”) as “running the function backwards” — going from output L to inputs X, Y. But as you write, the truth is that Prolog is modeling the relation of concatenation.
• masklinn 7y ago
  > Is one of these an un-idiomatic way to do it? I think the Scheme version might be considered unidiomatic due to the inefficiency: because it's not tail recursive, you're building a huge stack of cons calls (whose depth is the length of `as`) which only resolve once you reach the end of `as`. On the other hand, the version with accumulator would need to traverse as and bs in full, twice (once for the accumulation and once for the terminal reverse).
  • soegaard 7y ago
    There is a difference between Racket and Scheme. In Racket you will never get a stack overflow. You can of course exhaust memory, if you allocate too much, but the stack is guaranteed not to overflow. > At the same time, recursion does not lead to particularly > bad performance in Racket, and there is no such thing as > stack overflow; you can run out of memory if a computation > involves too much context, but exhausting memory typically > requires orders of magnitude deeper recursion than would > trigger a stack overflow in other languages. These > considerations, combined with the fact that tail-recursive > programs automatically run the same as a loop, lead Racket > programmers to embrace recursive forms rather than avoid > them. https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html#%28part._.Recursion_versus_.Iteration%29 https://docs.racket-lang.org/guide/Lists__Iteration__and_Rec...
    • pflanze 7y ago
      > There is a difference between Racket and Scheme AFAIK the Scheme standard doesn't specify either behaviour. So, with regards to the standard both Racket and other Scheme implementations are free to implement this in whichever way they prefer. And the Scheme implementations that I'm using (Gambit-C, Chicken and Guile) all work the same as Racket. I only know of Bigloo (of about 10 years ago, maybe it changed?) as a Scheme implementation that uses the machine stack to implement Scheme continuation frames, and Bigloo (again back then) doesn't (didn't?) implement call/cc efficiently either. Arguably to implement the Scheme standard including call/cc efficiently the machine stack can't be used, thus any 'proper' Scheme implementation will behave like Racket. I've written lots of non-Racket Scheme code and my code always assumes that it won't run out of stack before running out of heap. Some Scheme implementations allocate stack frames more efficiently than cons cells thus the straight-forward solution (recursion, not iteration then reversion) is also the more efficient one. There is a tendency of claiming Racket is somehow fundamentally different from Scheme which sometimes feels a bit like a racket. I'm not opposed to Racket but think it would be better to take it as what it is, Scheme plus extensions and tooling, which most other Scheme implementations are as well. Racket may be doing that more extensively but I think it calling itself a different language should primarily be understood as a marketing ploy, or maybe as a move to justify moving ahead with own ideas without caring about the rest of the Scheme community.
• pankajdoharey 7y ago
  Actually pattern matching is easy to implement in fact its implementation is given in SICP Section 4A Pattern Matching and Rule Based Substitution. And most modern lisps have it.
• soegaard 7y ago
  FWIW there is of course pattern matching in Racket. The program is practically identical to the Haskell version. (define (concast as bs) (match as ['() bs] [(cons a as) (cons a (concat as bs))]))
• dreamcompiler 7y ago
  Looks right to me except the Scheme version is not tail-recursive, so there's a possibility of stack overflow.