Search code examples
prolog

Flatten list in Prolog

I am fairly new to Prolog and attempting an exercise to flatten a list. My attempt is below, I've seen other correct implementations, but I can't figure out what is wrong with mine in particular.

my_flatten(List,Flattened) :- my_flatten_acc(List,Flattened,[]).

%% When first arg is an empty list, just return the rest of what was previously flattened
my_flatten_acc([],Flattened,Flattened).

%% When first arg is a list, whose first element empty list
my_flatten_acc([[]|T],Flattened,Acc) :- my_flatten_acc(T,Flattened,Acc).

%% First arg is a list, whose first element is a nonempty list
my_flatten_acc([[H|T]|T2],Flattened,[H|Acc]) :- my_flatten_acc([T|T2],Flattened,Acc).

%% First arg is a list, but not any of the above
my_flatten_acc([H|T],Flattened,[H|Acc]) :- my_flatten_acc(T,Flattened,Acc).

This fails on pretty much all non-empty inputs "List", and I have no idea why.

I have seen correct implementations of flatten (Both in other questions here, and in p07 here where I first encountered the exercise), but I'm not asking for a correct implementation, I just want to figure out what I've misunderstood in my attempt above.

Thanks!

Solution

  • Query ?- my_flatten([[1,2],[3,4]], Result). and which of the my_flatten_acc helper predicates can match?

    my_flatten_acc([[1,2],[3,4]], Flattened, []). % the helper call

my_flatten_acc([],        Flattened, Flattened). % no, first arg mismatch
my_flatten_acc([[]|T],    Flattened, Acc).       % no, first arg mismatch
my_flatten_acc([[H|T]|T2],Flattened, [H|Acc]).   % no, third arg mismatch
my_flatten_acc([H|T],     Flattened, [H|Acc]).   % no, third arg mismatch

    You aren't saying the accumulator starts as an empty list; lists are immutable so you're saying it must be an empty list, which makes it little use as an accumulator.

    Trace from https://swish.swi-prolog.org using query trace, my_flatten([[1,2],[3,4]], F). shows it fails very early:

    https://swish.swi-prolog.org trace