1

I am trying to implement the function tails. This is my attempt: 

tails' :: [a] -> [[a]]
tails' [] = []
tails' (x:xs) = xs:[[tails' xs]]

I keep running into compilation errors:

Couldn't match expected type ‘a’ with actual type ‘[[a]]’
      ‘a’ is a rigid type variable bound by
          the type signature for tails' :: [a] -> [[a]] at..

What is wrong with my implementation?

duplode
  • 33,731
  • 7
  • 79
  • 150
Ashwin
  • 12,691
  • 31
  • 118
  • 190
  • 2
    By your type signature, `tails' xs` must already be a list of lists. Enclosing it in brackets as `[[tails' xs]]` wraps that list of lists in two extra singleton lists. All you need is `tails' (x:xs) = xs:tails' xs`. – Alec Jan 03 '17 at 17:01
  • @Alec : You are right. It works. But I still don't get it why the brackets should be removed (aside from the fact that it makes the program work:)). Isn't it the job of the programmer to ensure that the returned value matches the one in type signature?? Because the way you are putting : type signature takes care of converting it into a list of lists – Ashwin Jan 04 '17 at 02:30
  • (1) Closely related: [*Why doesn't this function work if I use “\[xs\]” instead of “xs”?*](https://stackoverflow.com/q/48884276/2751851) (2) While the answer you have accepted covers your immediate issue, its solution is wrong -- for instance, `tails [] = [[]]` and `head (tails xs) = xs` are supposed to hold. I recommend switching the accept mark to another answer. – duplode Mar 16 '18 at 20:37

5 Answers5

6

Replace

tails' (x:xs) = xs:[[tails' xs]]

with:

tails' (x:xs) = xs : tails' xs
Leandro Galvan
  • 342
  • 1
  • 12
  • 2
    You don't even need the parens: `xs : tails' xs` works fine. – melpomene Jan 03 '17 at 17:19
  • @Leandro Galvan : Can you please explain why you removed the brackets? – Ashwin Jan 04 '17 at 02:27
  • 1
    @Ashwin the term `tails' xs` without the brackets is already a list of lists, i.e., of type `[[a]]`. It's a little confusing because the function is recursive, but if you look at the type you declared, it reads __tails' takes a list and returns a list of lists__; since `xs` is a list, applying it to `tails'` yields a list of lists. – Leandro Galvan Jan 04 '17 at 13:15
  • 2
    another quibble - to be the same as `Data.List.tails`, `head (tails xs) == xs` – rampion Mar 16 '18 at 22:47
5

Aside from the syntax type error, your implementation is not correct (to the spec). Compare it with this one...

Prelude> let tails [] = [[]]
Prelude|     tails y@(x:xs) = y:(tails xs)
Prelude|
Prelude> tails "abc"
["abc","bc","c",""]
karakfa
  • 66,216
  • 7
  • 41
  • 56
  • Even your implementation is not to-spec. Compare the result of `null (tails undefined)` between your implementation and `Data.List`'s. – Daniel Wagner Jan 03 '17 at 18:35
  • @DanielWagner I see how the implementation in Data.List manages to return `False` for that input, but why is it a useful property that `tails undefined = undefined : tails (tail undefined)`? – amalloy Jan 04 '17 at 01:24
  • 1
    @amalloy Let me turn the question around on you: why is it useful to be more strict than necessary? – Daniel Wagner Jan 04 '17 at 02:23
1

It's been over a year now but no correct answers were given so here's my take on it.

Let's start with the type signature:

tails' :: [a] -> [[a]]

This sugests that tails' should return a list-of-lists. The terminal case you syggested is just an empty list. Change it to:

tails' [] = [[]]

Now, the general case. Let's assume that our tails' works the way we want it to:

tails' []      -> [[]]
tails' [1]     -> [[1], []]
tails' [2,1]   -> [[2,1], [1], []]
tails' [3,2,1] -> [[3,2,1], [2,1], [1], []]

As we can see, we want to include the original list and the empty list. This means that given an input list xs, we want to concatenate xs onto something else.

But what's that something else? Let's do a bit of pseudo-haskell math:

let A = tails' [3,2,1] = [[3,2,1], [2,1], [1], []]
let B = tails' [2,1] = [[2,1], [1], []]
=> A = [[3,2,1], B] -- (1)

tail [3,2,1] == [2,1]
=> B = tails' (tail [3,2,1]) -- (2)

By (1) and (2)
A = [[3,2,1], tails' (tail [3,2,1])]
=> tails' [3,2,1] = [[3,2,1], tails' (tail [3,2,1])] -- (3)

By replacing [3,2,1] in (3) with xs
tails' xs = [xs, tails' (tail xs)]

Translating all this into Haskell gives us:

tails' :: [a] -> [[a]]
tails' [] = [[]]
tails' xs = xs : (tails' $ tail xs)


main = do
  print $ tails' [1,2,3]

-- [[1,2,3],[2,3],[3],[]]
zhirzh
  • 3,273
  • 3
  • 25
  • 30
  • 2
    While this is a good answer, I'm not sure that "no correct answers [had been] given". The solution you arrive at is essentially the same as [the one by karafka](https://stackoverflow.com/a/41448891/2751851), down to the detail about strictness mentioned by Daniel Wagner. – duplode Mar 16 '18 at 20:30
1

tails is the canonical example with simple lists for the recursion scheme called paramorphism. The following example uses the recursion-schemes library from Edward Kmett:

import Data.Functor.Foldable
import Data.List (tails)                      -- just for our test

paratails :: [a] ->  [[a]]
paratails = para alg where
    alg :: ListF a ([a], [[a]]) -> [[a]]
    alg (Cons x (hs, res)) = (x : hs) : res
    alg Nil = [[]]

-- $
-- >>> paratails [1,2,3,4]
-- [[1,2,3,4],[2,3,4],[3,4],[4],[]]
-- >>> paratails []
-- [[]]
-- >>> paratails [1,2,3,4] == (tails [1,2,3,4])
-- True
-- >>> paratails [] == (tails [])
-- True

Note: To shorten the code, you may use LambdaCase. With this extension, however, you cannot specify the type signature of the alg function

Jogger
  • 1,617
  • 2
  • 12
  • 22
  • 1
    "With [`LambdaCase`], however, you cannot specify the type signature of the alg function" -- I tried that over here and it worked fine (I kept the `alg` definition in the `where` clause, though). – duplode Mar 26 '18 at 04:03
1

As there now is a recursion-schemes fold answer, I feel obliged to add a recursion-schemes unfold answer:

import Data.Functor.Foldable

tailsApo :: [a] -> [[a]]
tailsApo = apo coalgTails
    where
    coalgTails = \case
        [] -> Cons [] (Left [])
        li@(_:xs) -> Cons li (Right xs)

I have used an apomorphism instead of a plain anamorphism because we don't want to produce an empty list out of an empty list (tails [] == [[]]).

duplode
  • 33,731
  • 7
  • 79
  • 150