haskell,recursion , Recursion in Haskell

Recursion in Haskell


Tag: haskell,recursion

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.


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
        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"]

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


Scala first program issue

I have just started to learn Scala after some experience with functional programming in other languages. def freq(c:Char, y:String, list:List[(Char,Int)]): List[(Char,Int)] = list match{ case _ => freq(c, y.filter(_ == c), list :: List((count(c,y),c))) case nil => list } In the above code I am getting an error when trying...

First three items of a list in Haskell

I am very new to Haskell, and struggling a bit with a function here. The premise is simple enough: Run through a list, and combine each 3 items next to each other with another function and return a list with the results. The problem is to do it in a...

Recusively count children nodes in binary tree

So my coding exercise is given the reference to the node count its children. I've decided to use recursion and I was wondering is this a elegant way to do this: Let's assume there is class Node which represent every node in the tree: public Node { int data: Node...

How do I avoid writing this type of Haskell boilerplate code

I run into this situation often enough for it to be annoying. Let's say I have a sum type which can hold an instance of x or a bunch of other things unrelated to x - data Foo x = X x | Y Int | Z String | ...(other...

How to flatten a structure of embedded Set and Hash

I would like to convert an embedding structure into a flat one. An embedding structure is a set of 0 or more objects, such as: a string or a hash having some string as key and some other embedding structure as value. A flat structure is a set of arrays...

Replace all [ ] with {} - as short as possible [on hold]

Given the code below: import Data.List; main = (readLn :: IO [Integer]) >>= print . subsequences It takes a list of integers from standard input (for example [1,2,3]) and outputs something like: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] I want it to be like this: {},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}} so my goal is to replace every [ and...

Stopping condition on a recursive function - Haskell

So, I have this function which aims to align the text on the left without cutting words(only white spaces). However my problem is that I cannot find a stopping condition of the function and it goes infinitely. f n "" = "" --weak condition f n s = if n...

Decremented value called in the recursion in Haskell

So, I have this function that aligns the text to the left for a given column width. I have already fixed some of its problems, but I am unable to make it not use the decremented parameter once it is called, but to return to the starting value of n....

Haskell IO - read from standard input directly to list

Haskell IO system is super hard to understand for me so i have question : How to read from standard input to list ? I know that there is function getLine :: IO String and interact. But i do not know how to convert the input to list so I...

Python RuntimeError: maximum recursion depth exceeded in cmp

I have a complex data structure that I'm trying to process. Explanation of the data structure: I have a dictionary of classes. The key is a name. The value is a class reference. The class contains two lists of dictionaries. Here's a simple example of my data structure: import scipy.stats...

My function will log a value to the console, but it won't return the same value - why? [duplicate]

This question already has an answer here: Return value of recursive function is 'undefined' 1 answer I've created the following function to flatten a nested array: function steamroller(arr) { arr = arr.reduce(function(a, b, i){ return a.concat(b); },[]); if (!Array.isArray(arr[arr.length-1])) {console.log(arr); return arr;} steamroller(arr); } steamroller([1, [2], [3, [[4]]]]); The...

Haskell return lazy string from file IO

Here I'm back again with a (for me) really strange behaviour of my newest masterpiece... This code should read a file, but it doesn't: readCsvContents :: String -> IO ( String ) readCsvContents fileName = do withFile fileName ReadMode (\handle -> do contents <- hGetContents handle return contents ) main...

Recursive solution doesn't iterate correctly

I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

EXC_BAD_ACCESS error occurring when running recursive merge sort method in a thread

I'm having trouble with my C++ code in xCode. I've tried debugging and I can't fix it. I know it's roughly when my mergeSort() method calls my mergeNumbers() method. I know it's not the method itself because I've run the method without threading and it works just fine. It's when...

Too much recursion - jquery - autocomplete

So here is my autocomplete functionality: var selected; var itemAdded = false; $('.js-main-search').autocomplete({ minLength: 3, source: function(request, response) { $.getJSON('/dashboard/searchDocumentsAndCompanies.do', { q: request.term}, function(data) { if(data.length == 0){ data = [ {name: 'No matches found', resultType: 'COMPANY', noResults: true}, {name: 'No matches found', resultType: 'BRANCHES', noResults: true}, ]; } data.unshift({name:...

Python recursive function not recursing

I'm trying to solve a puzzle, which is to reverse engineer this code, to get a list of possible passwords, and from those there should be one that 'stands out', and should work function checkPass(password) { var total = 0; var charlist = "abcdefghijklmnopqrstuvwxyz"; for (var i = 0; i...

Keep track of loop without a counter

Say, I got a list which length can be odd or even. Every iteration , I remove two items from the list. If there is one or no item at the end, I end the execution. If I store (length list)/2 every loop, I will get e.g. [5,4,3...] for a...

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))

I'm trying to write a recursive algorithm that returns true if at least one array[i] == i. And false if there is no array[i] = i. Also, the parameters needed are (int * arr, int start, int end). So i'll be traversing the array with a pointer. For example: int...

Best practice for handling data types from 3rd party libraries in Haskell?

I'm just getting into my first real Haskell project of size (a web app), and I'm starting to run into issues with types from 3rd party libraries leaking all over my code. Here is a quick example: My Parser module imports Test.Parsec, and the exports a function (parseConfig) that returns...

Haskell do clause with multiple monad types

I'm using a graphic library in Haskell called ThreePennyUI. In this library the main function returns a UI monad object. This causes me much headache as when I attempt to unpack IO values into local variables I receive errors complaining of different monad types. Here's an example of my problem:...

R: recursive function to give groups of consecutive numbers

Given a sorted vector x: x <- c(1,2,4,6,7,10,11,12,15) I am trying to write a small function that will yield a similar sized vector y giving the last consecutive integer in order to group consecutive numbers. In my case it is (defining groups 2, 4, 7, 12 and 15): > y...

algorithm to get all combinations of splitting up N items into K bins

Assuming I have a list of elements [1,2,3,4,] and a number of bins (let's assume 2 bins), I want to come up with a list of all combinations of splitting up items 1-4 into the 2 bins. Solution should look something like this [{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4},...

Recursive function returns undefined when there is only one numerical possibility

The code below contains a recursive method which should always return 7 however it return undefined whenever it has to re-generate a number because the number generated was already contained within the array that is defined at the top of the code. My question is... why is this happening and...

Identifying methods that can be converted into a recursive method

I've been searching around to practice my recursion, however I've run out of practice problems on codingBat, and a few others. If you've got more suggestions, feel free to comment them! My question is how do YOU identify when a method can simply be turned into a recursive method, even...

Recurions: simple spiral with python turtle

I'm trying to recreate a function spiral() using recursion that takes the parameters initLen (pixel length of first side), N (angle connecting segments), and mult (a float amount indicating how much bigger/smaller each segment should be after each turn - ex: mult = 0.5 means each segment would be half...

Eloquent Javascript: DOM Animation snippet

I'm trying to understand everything that is happening in this little code example in Eloquent Javascript: The Document Object Model (Chapter 13), but I'm not clear on where exactly the value for "time" is being passed into the animate() function before the function itself gets passed into requestAnimationFrame(). What exactly...

Combining Event and an attribute in threepenny-gui

I have an Event String which I want to sink into a textarea. This works fine, but now I want to combine the current value of a checkbox selection to this string. First I did this by using checkedChange of the checkbox which works, but has a problem. If the...

Recursive Lag Column Calculation in SQL

I am trying to write a procedure that inserts calculated table data into another table. The problem I have is that I need each row's calculated column to be influenced by the result of the previous row's calculated column. I tried to lag the calculation itself but this does not...

BSTD inorder traversal produces erroneous behaviour

I have a BSTD implementation which is inserting values incorrectly and I can't find for the life of me what is going on. EXPECTED ACTUAL -------- ---------- Alex Janice Carlos Janice Elton Janice Janice Zidane Zidane Zidane Implementation private Node<K,E> insert(Node<K,E> node, K key, E elem) { if (node ==...

Haskell - generate and use the same random list

In Haskell, I'd like to generate a random list of Ints and use it throughout my program. My current solution causes the array to be created randomly each time I access/use it. How can I overcome this problem?...

Haskell: When declaring a class, how can I use a type variable that is not immediately in the constructors?

I want to define a function, <-? to check whether an element is in a list/set/map. module Test where import qualified Data.Map as Map import qualified Data.Set as Set class Memberable a where (<-?) :: b -> a -> Bool instance Memberable [x] where (<-?) = elem instance Memberable (Map.Map...

Haskell make recipe fails for Paradox theorem prover using GHC

I am trying to install the paradox theorem prover sourced from here. When I run the makefile this is the command that runs: ghc -optl -static -lstdc++ -I../instantiate -I../minisat/current-base ../minisat/current-base/Solver.or ../minisat/current-base/Prop.or ../instantiate/MiniSatWrapper.or ../instantiate/MiniSatInstantiateClause.or -fglasgow-exts -O2 -static -threaded -main-is Paradox.Main.main --make Paradox.Main -o paradox And it results in several errors like...

T-SQL Ordering a Recursive Query - Parent/Child Structure

I am trying (and failing) to correctly order my recursive CTE. My table consists of a parent-child structure where one task can relate to another on a variety of different levels. For example I could create a task (this is the parent), then create a sub-task from this and then...

How to “wrap” monadic return value

I have the following code: data APNSIdentifier = NoIdentifier | Identifier Word32 deriving (Show, Eq) newtype APNSItem = Item Put createNotificationIdentifierItem :: APNSIdentifier -> APNSItem <--- here createNotificationIdentifierItem (Identifier identifier) = do putWord8 3 putWord16be 4 putWord32be identifier How can I "wrap" the Put monad with an APNSItem? Do I...

How does ((a++,b)) work? [duplicate]

This question already has an answer here: What does the comma operator `,` do in C? 8 answers In the below block of code, I am trying to understand how the line return reverse((i++, i)) is working. #include <stdio.h> void reverse(int i); int main() { reverse(1); } void reverse(int...

Implementing map on a tree using fold

I am trying to implement a map using fold. I could do so in Haskell data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) foldTree :: Tree a -> b -> (b -> a -> b -> b) -> b foldTree EmptyTree d _ =...

Reversing an integer using recursive method in C++

I have this recursive function to reverse a positive integer. Anybody having an efficient algorithm to do the task using fewer recursive calls (but still using recursion), please post here! int countDigit (const int & _X) { if (_X < 10) return 1; return (countDigit(_X / 10) + 1); }...

How can I declare a counter inside of my recursive function? (Additive Persistence: Coderbyte)

While working through some Coderbyte challenges, I was able to solve the following problem recursively, but was hoping to get some feedback on how I can improve it. Have the function AdditivePersistence(num) take the num parameter being passed which will always be a positive integer and return its additive persistence...

3 X 3 magic square recursively

I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

Reverse Linked List recursively, why it is wrong

Problem: Reverse a singly linked list recursively. I know how to solve this problem, but one of my recursive methods is wrong, I can not figure out what's wrong with this code. Could anyone figure out that? Thanks a lot! Test case: Input: [1,2,3] Output: [3,1] Expected: [3,2,1] public class...

How does Frege generalize number literals?

It appears that Frege can evaluate 1/2 to return the Double value 0.5. The literal 1 is of type Int. It seems to be promoted to Double, which is a type in the Real class and thus knows the / operator. How does this happen? Is it using the Haskell...

Get each fibbonacci value in haskell

I'm learning haskell and I have the following code: fib a b = a : fib b (a + b) findFibSum = sum [x | x <- fib 1 2, mod x 2 == 0 && x < 100] If I run findFibSum nothing happens, it just sits there. Shouldn't...

R: split string into numeric and return the mean as a new column in a data frame

I have a large data frame with columns that are a character string of numbers such as "1, 2, 3, 4". I wish to add a new column that is the average of these numbers. I have set up the following example: set.seed(2015) library(dplyr) a<-c("1, 2, 3, 4", "2, 4,...

Recursion of Linked List

When given an array of integers, I'm trying to change each element with the product of the integers before it. For example, int[] array = {2,2,3,4}; is now: {2, 4, 12, 48}; I added each element to a LinkedList, and I'm trying to do this recursively. This is what I...

BAD_ACCESS during recursive calls in Swift

While toying with Swift, I've encountered a situation which crashes and I still not have figured out why. Let define: class TestClass { var iteration: Int = 0 func tick() -> Void{ if iteration > 100000 { print("Done!") return } iteration++ tick() } } The tick() function calls itself and...

sum of Digits through Recursion

I am trying to make a recursive function which should return the sum of digits. The function should have only one argument. So far I have this; public int sumDigits(int n) { if(n%10 == n) // last digit remains return n; else{ int rightdigit; rightdigit = n%10; // taking out...

apply a transformation with function inline

Starting from a simple case of "fold" (I used (+) but can be anything else): Prelude.foldl (+) 0 [10,20,30] is it possible apply an inline transformation similar to (that doesn't work): Prelude.foldl ((+) . (\x -> read x :: Int)) 0 ["10","20","30"] In case not, is there an alternative to...

How can I express foldr in terms of foldMap for type-aligned sequences?

I'm playing around with type-aligned sequences, and in particular I'm messing around with the idea of folding them. A foldable type-aligned sequence looks something like this: class FoldableTA fm where foldMapTA :: Category h => (forall b c . a b c -> h b c) -> fm a b...