12 Replies - 3725 Views - Last Post: 26 October 2011 - 01:10 PM

#1 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Implementing a join in Haskell

Posted 18 October 2011 - 09:39 AM

I'm trying to write a function to join a list of Strings with a delimiter. I wrote this one which works fine:

join list delim = ((foldr (++) "" (map (++ delim) list)))


I can't help but think it must be possible (and much simpler) using just a fold. Here is what I tried. It won't compile and is probably a schoolboy error. Is it possible to combine two concatenation operations in some way so that I can do this with just a fold?

join list delim = foldr (++ delim ++) "" list


I also tried this, which doesn't compile either.

join3 [] delim = ""
join3 list delim = head(list) ++ delim  ++ join3((tail list) delim)


The error message is below, and suggests I have done something silly with types, though I have no idea what.


    Couldn't match expected type `[Char]'
                with actual type `[Char] -> [Char]'
    In the return type of a call of `join3'
    In the second argument of `(++)', namely
      `join3 ((tail list) delim)'
    In the second argument of `(++)', namely
      `delim ++ join3 ((tail list) delim)'
Compilation failed.


Any insight as to how I could fix these pieces of code would be much appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Implementing a join in Haskell

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Implementing a join in Haskell

Posted 18 October 2011 - 10:00 AM

Regarding your first version: foldr (++) "" could just be written as concat. Also there's a lot of unnecessary parentheses there ("a lot" meaning "two pairs"). Also note that your first version doesn't really do the same as the other ones because it appends the delimiter to the end of the string as well.

The second version doesn't work because there simply are no operator sections for multiple operators. The easiest fix would be to spell it out as a lambda, i.e. \x acc -> x ++ delim ++ acc.

The third version doesn't work because you're misusing parentheses. You seem to think that you can invoke a function taking multiple arguments with fun(arg1 arg2). You can't. What this will do is call fun with one argument which is the expression in parentheses (i.e. arg1 arg2, which is a function call where arg1 is the function to be called and arg2 is the argument to that function. To call a function with multiple arguments write fun arg1 arg2, which is the same as (fun arg1) arg2, not fun (arg1 arg2).

Also you shouldn't use head and tail like this, but rather use pattern matching. Fixing the issues with parentheses and using pattern matching, you get this:

join3 [] delim = ""
join3 (x:xs) delim = x ++ delim  ++ join3 xs delim



PS: If instead of "" you return [] in the base case, your function will become more general and work with all lists of lists instead of just with lists of strings.
Was This Post Helpful? 2
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Implementing a join in Haskell

Posted 19 October 2011 - 02:51 AM

Thanks for the detailed reply!

So, my first one becomes either of these. The latter is obviously better but the first was a good exercise as I'm just learning.

join list delim = foldr (++) "" (map (++ delim) list)
join list delim = concat (map (++ delim) list)


The second becomes this. My tutorial hasn't got as far as lambdas so it's good to see an example (and see where it would be useful in my code)

join list delim = foldr (\x acc -> x ++ delim ++ acc) "" list


You are right about my knowledge of parentheses. I assumed they were similar to Java and C when calling functions. Thanks for putting me right! My tutorial hasn't covered pattern matching yet either but your code looks pretty intuitive. The third version becomes either of these:

join [] delim = []
join list delim = head list ++ delim  ++ join (tail list) delim
join [] delim = []
join (x:xs) delim = x ++ delim  ++ join xs delim


Regarding the comment that the first method is the only one that appends the delimiter to the end of the output, all of them seem to do that (at least in the corrected code).

Anyway, thanks for the help!
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Implementing a join in Haskell

Posted 19 October 2011 - 04:40 AM

View Postcfoley, on 19 October 2011 - 11:51 AM, said:

Regarding the comment that the first method is the only one that appends the delimiter to the end of the output, all of them seem to do that (at least in the corrected code).


Now that you mention it, yes, they do. I must have gotten momentarily confused. So never mind that.
Was This Post Helpful? 1
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Implementing a join in Haskell

Posted 19 October 2011 - 05:40 AM

Awesome, Cheers!
Was This Post Helpful? 0
  • +
  • -

#6 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Implementing a join in Haskell

Posted 19 October 2011 - 01:31 PM

you could also use concatmap which is just concat . map
Was This Post Helpful? 1
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Implementing a join in Haskell

Posted 19 October 2011 - 04:13 PM

Oh, I like. It's getting to the stage where it's almost more straightforward to just inline the function:

join list delim = concatMap (++ delim) list

Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Implementing a join in Haskell

Posted 19 October 2011 - 05:03 PM

maybe you will like intercalate better? it dose the same thing but with reversed arguments :P i thought there might be something to do this so i looked up all the functions in Data.List

join list delim = intercalate delim list


lol, is that what you wanted? you *can* just inline that now. in fact, if you change the arguments around you get just say...
join = intercalate


useful reading for list manipulation

edit: this is a little different actually becuase it doesn't add the delimiter to the end like the others do :/

to make it the same:
join delim = (++ delim) . intercalate delim

This post has been edited by ishkabible: 19 October 2011 - 05:28 PM

Was This Post Helpful? 1
  • +
  • -

#9 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Implementing a join in Haskell

Posted 24 October 2011 - 01:32 AM

@ishkabible flip intercalate
Was This Post Helpful? 1
  • +
  • -

#10 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Implementing a join in Haskell

Posted 24 October 2011 - 03:14 AM

ishkabible, I thought I had replied to you. Intercalate is perfect and I did inline it after I read your post. Thanks!
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Implementing a join in Haskell

Posted 24 October 2011 - 12:13 PM

@Raynes: i didn't think about that! i read about that in Learn You a Haskell but never used it. i guess it would be useful for contorting some functions to fit some higher order function.
Was This Post Helpful? 0
  • +
  • -

#12 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Implementing a join in Haskell

Posted 25 October 2011 - 02:31 AM

That is exactly what it is good for. :)
Was This Post Helpful? 0
  • +
  • -

#13 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Implementing a join in Haskell

Posted 26 October 2011 - 01:10 PM

i read about another interesting Haskell function of a similar ilk, :- it reverses the way the function is applied, it's used for readability however, it's basically $ flipped around.

[1,2,3] :- sum :- (* 3)


it was used as an example for tree traversal.

so that where getXTree is the same as goX
getRightTree(getLeftTree tree)

could be
tree :- goLeft :- goRight

neat, right?

This post has been edited by ishkabible: 26 October 2011 - 01:11 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1