# optimization of list comprehensions

Richard A. O'Keefe <>
Tue Mar 7 22:27:29 CET 2006

```"Ulf Wiger \(AL/EAB\)" <> 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.

```