4 ms·

> Except that Python does not optimize tail calls Tail call reversion optimization just exists so people can right 'for loops' in a manner that looks 'function

> Except that Python does not optimize tail calls Tail call reversion optimization just exists so people can right 'for loops' in a manner that looks 'functional' on the surface. Because that is what tail optimization does.. it turns your recursive function into a loop. So every time you write a for loop in Python just tell yourself that it's actually just a brilliantly optimized recursive function and you can get the same benefit. Functions are first class objects in python so you can, if you really want, write functional code. It just all kinda goes to shit when you start importing other people's libraries that demand classes and methods being used. Those libraries are just a major part of what benefit you get from using python. So I am not saying that any of this invalidates haskell or anything like that.

DonaldPShimoda 7y ago
> Tail call reversion optimization just exists so people can right 'for loops' in a manner that looks 'functional' on the surface. Uh... sorry, but I don't think that's right. The purpose of writing functions with tail recursion isn't "I want to write a for-loop but I want it to 'look' functional." The purpose of tail recursion is to make easy certain kinds of implementations. If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wrote a comment about this recently: [0]. When using recursively-defined data, it makes more sense to write the traversal functions recursively. Functional programming makes significant use of recursion because, when dealing primarily with functions and immutable data, recursion is the simplest tool for the job. > Functions are first class objects in python so you can, if you really want, write functional code. It just all kinda goes to shit when you start importing other people's libraries that demand classes and methods being used. Those libraries are just a major part of what benefit you get from using python. I guess that's one way of looking at it, yeah. But if Python had better support (and encouragement) of functional programming, it seems to me that we'd have more functionally-styled libraries. [0] https://news.ycombinator.com/item?id=20896327 https://news.ycombinator.com/item?id=20896327
- kbp 7y ago
  > If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wrote a comment about this recently: [0]. > [0] https://news.ycombinator.com/item?id=20896327 https://news.ycombinator.com/item?id=20896327 That example isn't tail recursive, though. The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. An iterative algorithm, whether written using lexical recursion or a for loop, would entirely remove the use of a stack, not just hide the stack in your language implementation. Converting an iterative algorithm between the two forms is a simple syntax transformation, and doesn't introduce bookkeeping like that. Converting a body recursive function to iterate with an in-language stack introduces a lot of noise even if you use tail recursion to do the iteration. The tail recursive Haskell version of your Python isn't much better: sumTree :: BTree -> Int sumTree t = sumTree' [t] 0 where sumTree' [] total = total sumTree' (Leaf v : rest) total = sumTree' rest (v + total) sumTree' (Branch v l r : rest) total = sumTree' (l : r : rest) (v + total)
  - DonaldPShimoda 7y ago
    > That example isn't tail recursive, though. Oh damn, you're completely right. My mistake! I guess I should've actually re-read my comment before linking here since they were about slightly different things haha. Oh well. > The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. For a sufficiently large input, Python will error due to its maximum stack recursion depth (default is 1000, I think), so a generic solution requires using an in-language stack or else modifying your Python configuration to circumvent the maximum. (Or using a different language, I suppose.) > The tail recursive Haskell version of your Python isn't much better I do find that less readable than the non-tail-recursive version I had written previously, but still easier to read than the Python version with an explicit stack. An alternative approach might be to use a zipper instead of a list, but that's probably (definitely) over-engineering the problem haha. Actually for fun I put together a zipper-y solution. It takes a lot of scaffolding, but if we assume the zipper stuff was already implemented then the `sumTree` solution itself is nice enough: data BTree = Leaf Int | Branch Int BTree BTree data Path = Top | InLeft Int Path BTree | InRight BTree Int Path type Location = (BTree, Path) data Direction = Up | Down goDownLeft :: Location -> Location goDownLeft (Leaf _, _) = error "down of Leaf" goDownLeft (Branch v l r, p) = (l, InLeft v p r) goDownRight :: Location -> Location goDownRight (Leaf _, _) = error "down of Leaf" goDownRight (Branch v l r, p) = (r, InRight l v p) goUp :: Location -> Location goUp (_, Top) = error "up of Top" goUp (l, InLeft v p r) = (Branch v l r, p) goUp (r, InRight l v p) = (Branch v l r, p) sumTree :: BTree -> Int sumTree t = sumTree' Down (t, Top) 0 sumTree' :: Direction -> Location -> Int -> Int sumTree' Down l r = case l of (Leaf v, _) -> sumTree' Up l (v + r) _ -> sumTree' Down (goDownLeft l) r sumTree' Up l r = case l of (_, Top) -> r (_, InLeft{}) -> sumTree' Down (goDownRight (goUp l)) r (_, InRight _ v _) -> sumTree' Up (goUp l) (v + r) I feel like there's maybe a way to implement this more efficiently (like with a better choice of zipper constructors), but I really don't have a ton of experience with zippers so this is what I came up with. Maybe you know a better way?

DonaldPShimoda 7y ago

> Tail call reversion optimization just exists so people can right 'for loops' in a manner that looks 'functional' on the surface. Uh... sorry, but I don't think that's right. The purpose of writing functions with tail recursion isn't "I want to write a for-loop but I want it to 'look' functional." The purpose of tail recursion is to make easy certain kinds of implementations. If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wrote a comment about this recently: [0]. When using recursively-defined data, it makes more sense to write the traversal functions recursively. Functional programming makes significant use of recursion because, when dealing primarily with functions and immutable data, recursion is the simplest tool for the job. > Functions are first class objects in python so you can, if you really want, write functional code. It just all kinda goes to shit when you start importing other people's libraries that demand classes and methods being used. Those libraries are just a major part of what benefit you get from using python. I guess that's one way of looking at it, yeah. But if Python had better support (and encouragement) of functional programming, it seems to me that we'd have more functionally-styled libraries. [0] https://news.ycombinator.com/item?id=20896327 https://news.ycombinator.com/item?id=20896327

kbp 7y ago
> If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wrote a comment about this recently: [0]. > [0] https://news.ycombinator.com/item?id=20896327 https://news.ycombinator.com/item?id=20896327 That example isn't tail recursive, though. The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. An iterative algorithm, whether written using lexical recursion or a for loop, would entirely remove the use of a stack, not just hide the stack in your language implementation. Converting an iterative algorithm between the two forms is a simple syntax transformation, and doesn't introduce bookkeeping like that. Converting a body recursive function to iterate with an in-language stack introduces a lot of noise even if you use tail recursion to do the iteration. The tail recursive Haskell version of your Python isn't much better: sumTree :: BTree -> Int sumTree t = sumTree' [t] 0 where sumTree' [] total = total sumTree' (Leaf v : rest) total = sumTree' rest (v + total) sumTree' (Branch v l r : rest) total = sumTree' (l : r : rest) (v + total)
- DonaldPShimoda 7y ago
  > That example isn't tail recursive, though. Oh damn, you're completely right. My mistake! I guess I should've actually re-read my comment before linking here since they were about slightly different things haha. Oh well. > The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. For a sufficiently large input, Python will error due to its maximum stack recursion depth (default is 1000, I think), so a generic solution requires using an in-language stack or else modifying your Python configuration to circumvent the maximum. (Or using a different language, I suppose.) > The tail recursive Haskell version of your Python isn't much better I do find that less readable than the non-tail-recursive version I had written previously, but still easier to read than the Python version with an explicit stack. An alternative approach might be to use a zipper instead of a list, but that's probably (definitely) over-engineering the problem haha. Actually for fun I put together a zipper-y solution. It takes a lot of scaffolding, but if we assume the zipper stuff was already implemented then the `sumTree` solution itself is nice enough: data BTree = Leaf Int | Branch Int BTree BTree data Path = Top | InLeft Int Path BTree | InRight BTree Int Path type Location = (BTree, Path) data Direction = Up | Down goDownLeft :: Location -> Location goDownLeft (Leaf _, _) = error "down of Leaf" goDownLeft (Branch v l r, p) = (l, InLeft v p r) goDownRight :: Location -> Location goDownRight (Leaf _, _) = error "down of Leaf" goDownRight (Branch v l r, p) = (r, InRight l v p) goUp :: Location -> Location goUp (_, Top) = error "up of Top" goUp (l, InLeft v p r) = (Branch v l r, p) goUp (r, InRight l v p) = (Branch v l r, p) sumTree :: BTree -> Int sumTree t = sumTree' Down (t, Top) 0 sumTree' :: Direction -> Location -> Int -> Int sumTree' Down l r = case l of (Leaf v, _) -> sumTree' Up l (v + r) _ -> sumTree' Down (goDownLeft l) r sumTree' Up l r = case l of (_, Top) -> r (_, InLeft{}) -> sumTree' Down (goDownRight (goUp l)) r (_, InRight _ v _) -> sumTree' Up (goUp l) (v + r) I feel like there's maybe a way to implement this more efficiently (like with a better choice of zipper constructors), but I really don't have a ton of experience with zippers so this is what I came up with. Maybe you know a better way?