optimization of list comprehensions

[Richard A. O'Keefe]

"Ulf Wiger \(AL/EAB\)" <ulf.wiger@REDACTED> provided
another example of uses of folding:
	expand(Tops, TIds) ->
	  lists:foldr(<{hairy function}>, [], Tops).
	
which is a foldr, not a foldl, and again, has a simple variable as
the list.
	expand(Tops, TIds) ->
	  lists:foldl(<{hairy function}>, [], Tops).

	mk_tops(TIds1, TIds2, Dir, SId, Acc) ->
	  lists:foldl(fun(TId1, Acc1) ->
	      lists:foldl(<{hairy function}>, Acc1, TIds2), Acc, TIds1).

where again we find simple variables for the list arguments.

Let's look at the example in a little more detail.

	mk_tops(TIds1, TIds2, Dir, SId)
	 when is_list(TIds1), is_list(TIds2) ->
	  [#ctxtTop{frTId = TId1, toTId = TId2,
	            dir = Dir, strId = SId} ||
	    TId1 <- TIds1,
	    TId2 <- TIds2,
	    TId1 =/= TId2].
	
	expand(Tops, TIds) ->
	  lists:foldr(
	    fun(#ctxtTop{frTId = '*', toTId = '*', dir = Dir, strId = SId}, Acc)
	->
	          Acc ++ mk_tops(TIds, TIds, Dir, Sid);
	       (#ctxtTop{frTId = T1, toTId = '*', dir = Dir, strId = SId}, Acc)
	->
	          Acc ++ mk_tops([T1], TIds, Dir, SId);
	       (#ctxtTop{frTId = '*', toTId = T1, dir = Dir, strId = SId}, Acc)
	->
	          Acc ++ mk_tops(TIds, [T1], Dir, SId)
	    end, [], Tops).
	
There is a common pattern here which we may be able to factor out:
	Acc ++ mk_tops(?1, ?2, Dir, SId)

    expand(Tops, TIds) ->
        lists:foldr(fun(#ctxtTop{frTID=F, toTId=T, dir=Dir, strID=SId}, Acc) ->
			{TIds1,TIds2} = case {F,T}
					  of {'*','*'} -> {TIds,TIds}
					   ; {_,  '*'} -> {[F], TIds}
					   ; {'*',_  } -> {TIds,[T] }
					end,
			Acc ++ mk_tops(TIds1, TIds2, Dir, SId)
		    end, [], Tops).
			
Now we can consider expanding mk_tops in-line.  We see that the
is_list(TIDs1), is_list(TIds2) guard is satisfied when is_list(TIds),
so we can push that back into expand.

    expand(Tops, TIds) when is_list(TIds) ->
        lists:foldr(fun(#ctxtTop{frTID=F, toTId=T, dir=Dir, strId=SId}, Acc) ->
			{TIds1,TIds2} = case {F,T}
					  of {'*','*'} -> {TIds,TIds}
					   ; {_,  '*'} -> {[F], TIds}
					   ; {'*',_  } -> {TIds,[T] }
					end,
			Acc ++
			[#ctxtTop{frTid=TId1, toTId=TId2, dir=Dir, strId=SId}
			|| TId1 <- TIds1, TId2 < TId2, TId2 =/= TId1]
		    end, [], Tops).
			
Let's suppose the order of the elements doesn't matter very much, then we
can replace this by a single list comprehension:

    expand(Tops, TIds) when is_list(TIds) ->
	[  #ctxtTop{frID=TId1, toTId=TId2, dir=Dir, strID=SId}
	|| #ctxtTop{frId=F,    toTId=T,    dir=Dir, strId=SId} <- Tops,
	   {TIds1,TIds2} = case {F,  T  }
	                     of {'*','*'} -> {TIds,TIds}
	                      ; {_,  '*'} -> {[F], TIds}
	                      ; {'*',_  } -> {TIds,[T] }
	                   end,
	   TId1 <- TIds1,
	   TId2 <- TIds2,
	   TId2 =/= Tid1].

If the order does matter, we might need an extra reverse.  But we don't
appear to need any folds, unless I have misunderstood the example.