Proper prefix function in Haskell

1
votes

I want to create a Haskell function that prints the prefixes of a list:

The function should do the following:

> prefixes "123"
["","1","12"]
> prefixes "1"
[""]

I have written the following code:

prefixes :: [a] -> [[a]]
prefixes [] = []:[]
prefixes f =  f : prefixes(init(f))

The function prints the entered string or character as a prefix and prints it in opposite direction. I want to remove it so when I enter "123" it should print as above and display in correct direction.

We can use:

reverse (drop 1 f)

command but I don't know how to implement it in my function.

Can you help me solve this so that it does prints it correctly.

3
haskell
Do not use reverse (drop 1 f), first of all it should be reverse (drop 1 (reverse f)), but more important, it will no longer work on infinite lists. – Willem Van Onsem
123 is a prefix of 123. – n. 1.8e9-where's-my-share m.
@n.m.: I think this function aims to yield proper prefixes. – Willem Van Onsem
Again, if this was for homework or your own understanding, then great. But, in real code, you should probably consider writing prefixes lst = init (inits lst) or the equivalent prefixes = init . inits which uses inits from Data.List (which, as noted in another comment, has a particularly good implementation since GHC 7.8.4). – K. A. Buhr

3 Answers

6
votes

Your base case is incorrect, the empty list has no proper prefixes. So clearly in the base case you must return the empty list for the function to be correct.

Now consider the recursive case. For one, it should always start with the empty list (because the prefixes of (x:xs) are always [[],...]). How can we construct the rest of the list (the non-empty prefixes of (x:xs)?

We want to use recursion, so how do we build the set of non-empty proper prefixes of (x:xs) from the set of proper prefixes of xs? Look at your example "123", the prefixes of "23" are ["", "2"], the non-empty prefixes we want to construct are ["1","12"], so we just add '1' to the head of each prefix of the tail.

So in the recursive case: empty list is a proper prefix, and also the head of the list added to any proper prefix of the tail.

Here is a piece of code that does what you want:

prefixes []     = []
prefixes (x:xs) = [] : map (x:) (prefixes xs)
0
votes

It looks like you want to know how to define a helper function which would call your original definition.

prefixes xs = reverse (drop 1 (prefixes' xs)) where
    prefixes' [] = []:[]
    prefixes' f =  f : prefixes' (init(f))

Your original definition, while seemingly working, is rather suboptimal though. The other answer shows how to do it more intuotively and without needing a helper function (edit: but the performance may or may not be any good). There are other small things that could be improved in this function:

  • []:[] can be written simply as [[]]
  • drop 1 is tail
  • parentheses can often be replaced by function composition and $ for better readability.
0
votes

Here is a solution in point-free style:

prefixes = foldr (\el acc -> [] : map (el:) acc) []