Search code examples
smlsmlnj

Connecting all elements in list with infix operator


So I have a list lets say [t, f, f, t, f] and an infix operator <==>. I want to connect the elements so the end result will look like this t <==> f <==> f <==> t <==> f . The problem that I am having though is that i get this result t <==> (f <==> (f <==> (t <==> f))). I know why this is happening because the resursion returns all previous elements but I have no idea how to fix it.

This is my code:

fun connect(l) =
    case l of
      x::[] => x
      | x::xs => x1 <==> connect(xs);

Solution

  • the end result will look like this t <==> f <==> f <==> t <==> f.

    problem is that i get this result t <==> (f <==> (f <==> (t <==> f)))

    x <==> y <==> z could mean either (x <==> y) <==> z or x <==> (y <==> z).

    If it is a problem that you fold to one side, try folding to the other:

    fun connectLeft (x::xs) = foldl (op <==>) x xs
    fun connectRight (x::xs) = foldr (op <==>) x xs
    

    You can see how foldl and foldr are implemented.

    Or you can see the illustration of folds as structural transformations (Wikipedia).


    Edit: Assuming x <==> y <==> z means (x <==> y) && (y <==> z):

    fun connect [] = ?
      | connect [x] = ?
      | connect [x,y] = x <==> y
      | connect (x :: y :: rest) =
          (x <==> y) && connect (y :: rest)
    
    • && is not the name of SML's built-in logical and-operator, which is called andalso. If x <==> y returns a bool, then perhaps you mean to use andalso here.
    • Since connect supposedly returns either a bool or some user-defined truthy value, then maybe connect [x] = x, but maybe not.
    • In any case, connect [] should be considered: Is there a good default here, so that the function does not crash on empty lists?

    If you want to write this using list combinators (like map, foldl, etc.) instead of manual recursion, what you can do is:

    1. Convert the input list into a list of pairs, so [x, y, z] becomes [(x, y), (y, z)]. There is an SML function called zip, hiding away in the library ListPair... a few examples that might hint at how to do this:

      ListPair.zip [x1,x2,x3] [y1,y2,y3] = [(x1,y1), (x2,y2), (x3,y3)]
      ListPair.zip [x1,x2,x3] [x1,x2,x3] = [(x1,x1), (x2,x2), (x3,x3)]
      ListPair.zip [x1,x2,x3] [y2,y3]    = [(x1,y2), (x2,y3)]
      
    2. Call map (op <==>) over the list of pairs.

    3. Fold over the result with some && operator.