2

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.

Improve this question
4
  • 2
    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. Commented Oct 8, 2018 at 7:48
  • 1
    123 is a prefix of 123. Commented Oct 8, 2018 at 7:56
  • @n.m.: I think this function aims to yield proper prefixes. Commented Oct 8, 2018 at 7:59
  • 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). Commented Oct 11, 2018 at 20:32

4 Answers 4

Reset to default
6

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

OP wants to know how to call reverse (drop 1 f) which would convert a list of prefixes he already has to a list of proper prefixes. Of course the method of obtaining prefixes OP's using is totally barbaric but the real problem IMHO is more basic than that.
0

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.
Improve this answer

Comments

0

Here is a solution in point-free style:

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

Comments

0

To avoid having a empty list and including the last element, you should write it like this:

preFix = foldr (\el acc -> [el] : map((:) el) acc) []
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.