Earlier quoted context omitted.
The Fish suggestion the GP is describing isn't based on history, although it also autocompletes from commands in your history that way. That's part of the baseline autocompletion functionality of the whole shell, for all command names, local files, etc.
Expanding on the local file competition: this is even context aware in some cases! If you have four files starting with "A", one of which ends in .gz, typing "gunzip A" will suggest the .gz file. Likewise for things like "git add" - as soon as you type an identifiable prefix to a changed file it will be suggested (eg if you only have one changed file in src/ it will suggest that when you type git add src)
> If you have four files starting with "A", one of which ends in .gz, typing "gunzip A" will suggest the .gz file.
Bash does this for me as well.