CODEWITHSUNDEEP
haskell
bob
bob

Reputation: 111

Proper prefix function in Haskell

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.

Upvotes: 2

Views: 1730

Answers (4)

AdrianSt
AdrianSt

Reputation: 21

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) []

Upvotes: 0

MiFi
MiFi

Reputation: 759

Here is a solution in point-free style:

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

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 120011

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.

Upvotes: 0

Jonas Duregård
Jonas Duregård

Reputation: 937

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)

Upvotes: 6

Related Questions