7 ms·

Assuming the data structure is a singly linked list than yes it's not stack safe. At a high level foldLeft and foldRight represent abstraction leakage. The Dom

Assuming the data structure is a singly linked list than yes it's not stack safe. At a high level foldLeft and foldRight represent abstraction leakage. The Domain and Codomain for both functions are exactly the same. If there is no performance difference or side effects to consider then there is almost no point in having two fold functions as a plain fold has the exact same inputs and outputs as foldLeft or foldRight. Typically for side effects you don't want to put it in a fold as you're integrating way too much IO with your functional computations. Rather functional languages tend to have something along the lines of "foreach" for using side effects on the content in a functor. That being said it's strange that scala has a foldLeft and a foldRight with identical performance characteristics. Maybe it's a legacy thing. I dunno, not a scala guy. Just bringing that up. I still agree with you that the interview question sucked and that the interviewer was wrong. Personally I wouldn't have ever figured out that was what the interviewer was looking for even when I do possess the requisite knowledge.

cottonseed 6y ago
> The Domain and Codomain for both functions are exactly the same. This is not true. > def List[A].foldLeft[B](z: B)(op: (B, A) => B): B > def List[A].foldRight[B](z: B)(op: (A, B) => B): B Notice the signature of the fold op: the arguments types are swapped. This is because fold left and right on a list [a, b], say, is the difference between: (z op a) op b and a op (b op z) (If this isn't compelling enough, consider [a, b, c].) Not all functions are associative. For example, consider a cryptographic hash function.
- leafboi 6y ago
  Elements in sets are not ordinal. In principle they are the same as the set (B, A) is the same set as (A, B). If you're saying that foldRight in scala exists aesthetic reasons... well can't argue with that. I figured it was more for legacy reasons as the original poster said that there use to be a performance difference. As for the associative thing I mentioned side effects. Function composition is always associative. Unless you have side effects. See: https://www.wikiwand.com/en/Function_composition https://www.wikiwand.com/en/Function_composition (search for associative) I don't know much about crypto but I'm assuming you're referring to things that aren't side effect free. In general though a hash function should be associative under function composition as it is just a surjective mapping from domain to codomain. Also can't exactly read that syntax nor the stuff below it. Not a scala dude. Maybe a more traditional map implementation in like python or JS pseudo code would make more sense to me, but that may be too much to ask. edit: I think you actually may be right. We're both a little wrong with our reasoning though. Function composition is not commutative. And FoldRight and FoldLeft reverses the order of composition which has an effect on operations that are not commutative.
  - jhanschoo 6y ago
    Parent wasn't slightly wrong, you just tunneled in on the signature of the operator function, when the reason why parent comment brought it up was to illustrate that the operator function is not necessarily associative, and that the function signature was meant to suggest the difference in associativity. You're wrong about the operations possibly not being commutative; as you pointed out, whether the parameter list is (A, B) or (B, A) doesn't really matter, so it doesn't pose a problem. An example is the subtraction operator: with just two elements, I can change `(a, b) => b - a` to `(b, a) => b - a` with with no difference in result. But there is no way I can write a subtraction function for foldLeft that gives the same results as a foldRight on subtraction in general. That is, I can write op such that a op b = b - a, but not that (a op b) op c = (c - b) - a. Nevertheless, I can still write op such that a op (b op c) = (c - b) - a due to some dual notion of commutativity.
    - leafboi 6y ago
      Function composition is associative but not commutative. So in essence given three functions z,g,f and composition operator <.> f . g . z != z . g . f (commutativity) which is sort of what fold left or right is doing (but with z g and f being the same function). but: f . g . z == z . (g . f) (associativity) My edit is right about the operations not being commutative. Parent is wrong about associativity as it has nothing to do with this, but he is right that the codomains of left and right are not equal. Function composition isn't completely accurate to what's going on, it's a more higher order form of composition going on with fold but the rules remain the same. Whatever, either way, Overall I'm wrong
      - roflc0ptic 6y ago
        But sincerely, thanks for commenting. If I'm walking around self righteously asserting incorrect stuff I much appreciate people pointing it out
      - jhanschoo 6y ago
        You're right. > which is sort of what fold left or right is doing (but with z g and f being the same function). > it's a more higher order form of composition More precisely, a fold performs function composition on the provided operator curried with the respective elements, so that z g and f above are different functions (hence not commutative in general, but associative in general, wrt folding).

cottonseed 6y ago

> The Domain and Codomain for both functions are exactly the same. This is not true. > def List[A].foldLeft[B](z: B)(op: (B, A) => B): B > def List[A].foldRight[B](z: B)(op: (A, B) => B): B Notice the signature of the fold op: the arguments types are swapped. This is because fold left and right on a list [a, b], say, is the difference between: (z op a) op b and a op (b op z) (If this isn't compelling enough, consider [a, b, c].) Not all functions are associative. For example, consider a cryptographic hash function.

leafboi 6y ago
Elements in sets are not ordinal. In principle they are the same as the set (B, A) is the same set as (A, B). If you're saying that foldRight in scala exists aesthetic reasons... well can't argue with that. I figured it was more for legacy reasons as the original poster said that there use to be a performance difference. As for the associative thing I mentioned side effects. Function composition is always associative. Unless you have side effects. See: https://www.wikiwand.com/en/Function_composition https://www.wikiwand.com/en/Function_composition (search for associative) I don't know much about crypto but I'm assuming you're referring to things that aren't side effect free. In general though a hash function should be associative under function composition as it is just a surjective mapping from domain to codomain. Also can't exactly read that syntax nor the stuff below it. Not a scala dude. Maybe a more traditional map implementation in like python or JS pseudo code would make more sense to me, but that may be too much to ask. edit: I think you actually may be right. We're both a little wrong with our reasoning though. Function composition is not commutative. And FoldRight and FoldLeft reverses the order of composition which has an effect on operations that are not commutative.
- jhanschoo 6y ago
  Parent wasn't slightly wrong, you just tunneled in on the signature of the operator function, when the reason why parent comment brought it up was to illustrate that the operator function is not necessarily associative, and that the function signature was meant to suggest the difference in associativity. You're wrong about the operations possibly not being commutative; as you pointed out, whether the parameter list is (A, B) or (B, A) doesn't really matter, so it doesn't pose a problem. An example is the subtraction operator: with just two elements, I can change `(a, b) => b - a` to `(b, a) => b - a` with with no difference in result. But there is no way I can write a subtraction function for foldLeft that gives the same results as a foldRight on subtraction in general. That is, I can write op such that a op b = b - a, but not that (a op b) op c = (c - b) - a. Nevertheless, I can still write op such that a op (b op c) = (c - b) - a due to some dual notion of commutativity.
  - leafboi 6y ago
    Function composition is associative but not commutative. So in essence given three functions z,g,f and composition operator <.> f . g . z != z . g . f (commutativity) which is sort of what fold left or right is doing (but with z g and f being the same function). but: f . g . z == z . (g . f) (associativity) My edit is right about the operations not being commutative. Parent is wrong about associativity as it has nothing to do with this, but he is right that the codomains of left and right are not equal. Function composition isn't completely accurate to what's going on, it's a more higher order form of composition going on with fold but the rules remain the same. Whatever, either way, Overall I'm wrong
    - roflc0ptic 6y ago
      But sincerely, thanks for commenting. If I'm walking around self righteously asserting incorrect stuff I much appreciate people pointing it out
    - jhanschoo 6y ago
      You're right. > which is sort of what fold left or right is doing (but with z g and f being the same function). > it's a more higher order form of composition More precisely, a fold performs function composition on the provided operator curried with the respective elements, so that z g and f above are different functions (hence not commutative in general, but associative in general, wrt folding).