%%% prob(+W,+S,?P) probability of a given symbol sequence W and state sequence S

% ?- prob([h,a],[s1,s2],P).

%%% Task 2: Total probability

%?- findall(P, prob([h,a,h,a,h,a,!],S,P), Ps), sum_list(Ps, TotalProb).

%%% Task 3: Total probability

%?- findall(P-S, prob([h,a,h,a,h,a,!],S,P), Pairs), max_key(Pairs,MaxP-MaxS).

prob(W, S, P) :-
  prob(W, [s0|S], 1.0, P).
  
prob([],[St], P0, P):-
  a(St, se, A),
  P is P0*A.
prob([W1|W], [S1,S2|S], P0, P) :-
  a(S1, S2, A),
  b(S2, W1, B),
  P1 is P0*A*B,
  prob(W, [S2|S], P1, P).





% utility predicates

max_key([First|Rest],Max) :-
	max_key_accu(Rest, First, Max).

max_key_accu([],Max,Max).
max_key_accu([Num1-Val1|Rest],Num2-Val2, Max) :-
	( Num1 > Num2
	->	max_key_accu(Rest, Num1-Val1,Max)
	;	max_key_accu(Rest, Num2-Val2, Max)
	).

sum_list(List, Sum) :-
	sum_list(List, 0, Sum).

sum_list([], Sum, Sum).
sum_list([Head|Tail], Sum0, Sum) :-
	Sum1 is Head+Sum0,
	sum_list(Tail, Sum1, Sum).