{"action":"created","issue":{"url":"https://api.github.com/repos/fpinscala/fpinscala/issues/442","labels_url":"https://api.github.com/repos/fpinscala/fpinscala/issues/442/labels{/name}","comments_url":"https://api.github.com/repos/fpinscala/fpinscala/issues/442/comments","events_url":"https://api.github.com/repos/fpinscala/fpinscala/issues/442/events","html_url":"https://github.com/fpinscala/fpinscala/issues/442","id":119116118,"number":442,"title":"Alternative solution to 3.6","user":{"login":"numesmat","id":752516,"avatar_url":"https://avatars.githubusercontent.com/u/752516?v=3","gravatar_id":"","url":"https://api.github.com/users/numesmat","html_url":"https://github.com/numesmat","followers_url":"https://api.github.com/users/numesmat/followers","following_url":"https://api.github.com/users/numesmat/following{/other_user}","gists_url":"https://api.github.com/users/numesmat/gists{/gist_id}","starred_url":"https://api.github.com/users/numesmat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/numesmat/subscriptions","organizations_url":"https://api.github.com/users/numesmat/orgs","repos_url":"https://api.github.com/users/numesmat/repos","events_url":"https://api.github.com/users/numesmat/events{/privacy}","received_events_url":"https://api.github.com/users/numesmat/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-11-27T01:22:31Z","updated_at":"2015-11-28T03:32:27Z","closed_at":null,"body":"I initially focused on solving 3.6 task with some kind of tail recursion to avoid potential stack overflow.\r\nAfter I wrote my own implementation I checked the answer, and its optimized variant (init2) uses mutable buffer.\r\nIs there any problem with my variant? Is init2 with mutable buffer implementation better and why / in which case (if not in all)? Here is my variant\r\n```scala\r\ndef init[A](l: List[A]): List[A] = {\r\n    def loop(l: List[A], n: List[A]): List[A] = {\r\n      l match {\r\n        case Nil => append(n, Nil)\r\n        case Cons(h, Nil) => append(n, Nil)\r\n        case Cons(h, t) => loop(t, append(n, List(h)))\r\n      }\r\n    }\r\n\r\n    l match {\r\n      case Nil => Nil\r\n      case Cons(h, Nil) => Nil\r\n      case Cons(h, t) => loop(t, List(h))\r\n    }\r\n}\r\n```"},"comment":{"url":"https://api.github.com/repos/fpinscala/fpinscala/issues/comments/160243649","html_url":"https://github.com/fpinscala/fpinscala/issues/442#issuecomment-160243649","issue_url":"https://api.github.com/repos/fpinscala/fpinscala/issues/442","id":160243649,"user":{"login":"jvliwanag","id":211068,"avatar_url":"https://avatars.githubusercontent.com/u/211068?v=3","gravatar_id":"","url":"https://api.github.com/users/jvliwanag","html_url":"https://github.com/jvliwanag","followers_url":"https://api.github.com/users/jvliwanag/followers","following_url":"https://api.github.com/users/jvliwanag/following{/other_user}","gists_url":"https://api.github.com/users/jvliwanag/gists{/gist_id}","starred_url":"https://api.github.com/users/jvliwanag/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jvliwanag/subscriptions","organizations_url":"https://api.github.com/users/jvliwanag/orgs","repos_url":"https://api.github.com/users/jvliwanag/repos","events_url":"https://api.github.com/users/jvliwanag/events{/privacy}","received_events_url":"https://api.github.com/users/jvliwanag/received_events","type":"User","site_admin":false},"created_at":"2015-11-28T03:32:27Z","updated_at":"2015-11-28T03:32:27Z","body":"Within your `loop`, you only need `append` on the last case. However, `append` itself runs linearly. Since `loop` is also called ~n times, you end up with with your init function being O(n<sup>2</sup>)."}}