Recursion in Haskell

Question

I'm still learning Haskell and I'm doing a few exercises, but I'm in a jam. So I have a function called "novel" which takes 2 Strings and an Int (novel :: (String, String, Int) -> String) for its arguments. Novel's input/output must look like the following:

> novel ("Rowling", "Harry Potter", 1998)
"Harry Potter (Rowling, 1998)"

This is my code for my novel function which works as explained above:

novel :: (String, String, Int) -> String
novel (author, book, year) = book ++ " (" ++ author ++ ", " ++ (show year) ++ ")"

I am trying to write a new function called, "cite" (cite :: [(String, String, Int)] -> String). Cite's input/output should look like the following:

> cite [("author1", "book1", year1), ("author2", "book2", year2), ("author3", "book3", year3)]
"book1 (author1, year1)
book2 (author2, year2)
book3 (author3, year3)"

I am trying to use "novel," recursively, in order to get the desired output, but I am not sure how to go about this.

What I've tried:

cite :: [(String, String, Int)] -> String                -- | Listed arguments
cite [] = ""                                             -- | Base Case
cite x:xs = [(novel (author, book, year)), (novel (author, book, year)), (novel (author, book, year))]

This is honestly as far as I got. Obviously, it doesn't work, but I am not sure what to do from here.

Do you want it to return String (i.e. [Char]) which uses "\n" in between each citation, or do you want to return [String]? — TheCriticalImperitive
– TheCriticalImperitive, Commented Jan 11, 2015 at 4:33
I don't understand how map would help me here. What I understand of map is that it takes a function and a list and you can manipulate items in that list with arithmetic operations. — Joffrey Baratheon
– Joffrey Baratheon, Commented Jan 11, 2015 at 4:33
@TheCriticalImperitive I'm not returning a list. I'm returning a String. It's returning it the same way that novel is returning it. — Joffrey Baratheon
– Joffrey Baratheon, Commented Jan 11, 2015 at 4:34
@JoffreyBaratheon map can perform any operation to the items of a list, not just arithmetic. A String is the same as a list of Chars in Haskell. In fact, the type String is just a synonym for [Char]. — David Young
– David Young, Commented Jan 11, 2015 at 5:04

TheCriticalImperitive · Accepted Answer · 2015-01-11 05:04:15Z

Perhaps this will give you a head start:

cite :: [(String, String, Int)] -> String
cite [] = ""
cite (x:xs) = undefined -- put your code that recursively calls cite in here, hint: use ++ and "\n\"

The pattern match (x:xs) says this, give me the first item in the list x and the tail of the list xs. It would be the same as writing this:

cite xs' = let x = head xs'
               xs = tail xs'
           in  undefined -- your code here

Or even

cite xs' = undefined -- your code here
    where
        x = head xs'
        xs = tail xs'

Hope that helps push you in the right direction.

EDIT: OP asked for how to do this recursively, below is my original answer:

You should probably re-write your base case to say cite [] = "". It doesn't really make a difference, but it will help with code readability.

Let's start by putting ":t map novel" into ghci to see what you get:

> :t map novel
map novel :: [([Char], [Char], Int)] -> [[Char]]

Which we can rewrite as: map novel :: [(String, String, Int)] -> [String]

How? Because map does a transformation of one type a to another type b and applies it to every item in a list. The first argument of map is any function which takes one argument. Exactly what novel does.

But that doesn't give us what you need, we'll end up with a list of Strings instead of a String:

> cite [("author1", "book1", year1), ("author2", "book2", year2), ("author3", "book3", year3)]
["book1 (author1, year1)","book2 (author2, year2)","book3 (author3, year3)"]

And you would like it to be a single string separated by a newline character "\n". Is there a function that can take a list of strings and concatenate them into one string, but intercalate a separator between them?

First let's describe such a function: String -> [String] -> String. Next we chuck it into Hoogle to see what we get: https://www.haskell.org/hoogle/?hoogle=String+-%3E+%5BString%5D+-%3E+String

Ah, that second function intercalate sounds like what we need. It doesn't just work on Strings, it works on any list. How would it work? Something like this:

> import Data.List (intercalate)
> intercalate "\n" ["List","Of","Strings"]
"List\nOf\nStrings"

So now you can combine intercalate and map to get what you are after. I'll leave the definition for cite up to you.

EDIT: Completely forgot, there is actually a specialised function for this. If you just search for [String] -> String in Hoogle you'll find unlines

I'm trying to do this recursively, though. I found some pdf text that I'm following and I'm on a chapter for recursion and mapping is the next one. It's telling me to do this purely recursively. And it didn't say anything about having to import anything.
Ah, if you haven't learned about map yet then the above would be introducing too much too soon. See my updated answer.
I don't understand what you mean by, "use ++ and "\n\"." I'm supposed to use the novel function in there. I have to use novel in the recursion. I apologize if I wasn't clear. Thank you for taking the time out of your day for this.
A very common pattern is something like this: recur (x:xs) = x ++ recur xs. So take out the first item, do something to it then call your original function with the rest of the list.
I'll leave the answer at the end of this comment. If you get really stuck take a look. It can be pretty frustrating when you just draw a blank and you just want to move on, so if you reach that point the answer is..................: cite (x:xs) = novel x ++ "\n" ++ cite xs

AJF · Accepted Answer · 2015-01-11 14:00:46Z

There's a reasonably simple way of doing this.

First, map novel to each element of the given list, then use Data.List.intersperse to fill the gaps with newlines. This is my implementation:

import Data.List (intersperse)

cite :: [(String, String, Int)] -> String
cite bs = intersperse '\n' (map novel bs)

Or, in a more elegant points-free style:

cite = intersperse '\n' . map novel

One could also write a nice, efficient recursive function:

cite []     = ""
cite [x]    = novel x
cite (x:xs) = novel x ++ '\n' : cite xs

In future problems such as this, keep in mind functions such as map and foldr - these are two of the most integral parts of Haskell and functional programming. Also, your pattern matches need to be enclosed in parentheses.

Collectives™ on Stack Overflow

Recursion in Haskell

2 Answers 2

8 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Related